j剑指offer面试题[33]-把数组排成最小的数

╰半夏微凉° 2022-06-12 13:38 72阅读 0赞

## 题目描述 ##

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

思路：

可以求出这个数组中所有数字的全排列，然后把每个排列拼起来，最后求出拼起来的数字的最小值。根绝数组排列组合的思想，n个数字总共有n！个排列。还有更快的方法，一个非常直观的办法就是把数字转换为字符串。由于把数字m和n拼接起来得到nm和mn，他们的位数肯定是相同的，因此比较他们的大小只需要按照字符串大小的比较规则就可以了。**用sort实现时，需要自定义比较规则函数**。因为我们比较的不是输入的两个字符串a和b，而是ab和ba两种组合的大小。 这种规则的有效性剑指offer上面给出了详细的证明。

class Solution {
    public:
        string PrintMinNumber(vector<int> numbers) {
           int length=numbers.size();
           stringstream stream;
           //string *str=new string[length];
           vector<string> vec;
           for(int i=0;i<length;i++)
            {
                //方法1：用to_string将数字转换为字符串
                vec.push_back(to_string(numbers[i]));
                //方法2:借助借助字符串流stringstream将数字转换为字符串
                /*string str;
                stream<<numbers[i]; 
                stream>>str;
                vec.push_back(str);
                stream.clear();   //记得要清空
                */
            }
           sort(vec.begin(),vec.end(),comp);
           string result;
           for(int i=0;i<length;i++)
             { 
                 result+=vec[i];
             }
            return result;
        }
         static bool comp(string str1,string str2)  //若comp函数放在外面则可以去掉static关键字，原因如下:
         {                             //sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。
                                       //因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调
            string s1=str1+str2;       //用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何
            string s2=str2+str1;       //对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。
            return s1<s2;
         }
    };