JZ32 题解 | #把数组排成最小的数#

题意分析

• 首先，给我们一个数组，需要我们将这个数组进行一个排列，然后对数组的所有的数字按照排列的顺序进行拼接，拼接成字符串，问我们得到的最小的字符串。

思路分析

解法一 全排列

• 既然说了存在一种排列的方式使得最后的结果最小，那么就可以使用全排列进行求解，我们利用全排列来枚举所有的情况，然后我们对每种排列情况组成的字符串进行存储，最后对所有存储的字符串进行排序，选出最小的字符串就行了。对于全排列，C++已经有了现成的库函数可以调用，当然也可以自己利用DFS实现全排列。这里我就偷一点懒。同时要注意的是对动态数组的全排列需要我们先对动态数组进行升序排列。这样才会枚举出所有的情况。
• 代码如下
  • 需要对数组进行全排列，根据排列组合的知识，全排列的时间复杂度为O(n!)
  • 需要用数组存储所有的数字，空间复杂度为O(n)

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        vector<string> ans;
        // 先对数组进行升序排列
        sort(numbers.begin(),numbers.end());
        // 利用库函数枚举所有的排列的情况
        do{
            string now="";
            // 对这种排列组成的字符串进行存储
            for(auto x:numbers){
                string tmp="";
                while(x){
                    tmp+=(x%10+'0');
                    x/=10;
                }
                reverse(tmp.begin(),tmp.end());
                now+=tmp;
            }
            ans.push_back(now);
        }while(next_permutation(numbers.begin(),numbers.end()));
        // 排序选出最大的那个
        sort(ans.begin(),ans.end());
        return ans[0];
    }
};

解法二 交换比较

• 假设我们存在两个数字x和y，加入x+y组成的字符串大于y+x组成的字符串，那么就说明我们需要将这两个字符串交换位置。那么我们就可以使用双重循环进行枚举。一次找出每个位置应该存放的最优的那个数。
• 代码如下
  • 需要双重for循环对数组进行遍历进行两两比较，时间复杂度为O(n^2)
  • 需要用数组存储n个数字，空间复杂度为O(n)

class Solution {
public:
     // 对两个数字判断是否需要交换位置
    bool judge(int x,int y){
        string tmpx="";
        while(x){
            tmpx+=(x%10+'0');
            x/=10;
        }
        // 进行二进制拆解的最后记得反转
        reverse(tmpx.begin(),tmpx.begin());
        string tmpy="";
        while(y){
            tmpy+=(y%10+'0');
            y/=10;
        }
        reverse(tmpy.begin(),tmpy.begin());
        return tmpx+tmpy>tmpy+tmpx;
    }
    string PrintMinNumber(vector<int> numbers) {
        int len=numbers.size();
        // 双重循环进行两两比较
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(judge(numbers[i],numbers[j])){
                    // 如果返回为true，就说明我们需要进行交换
                    swap(numbers[i],numbers[j]);
                }
            }
        }
        string ans="";
        // 最后这个序列就是一个最优的序列
        for(auto x:numbers){
            string tmp="";
            while(x){
                tmp+=(x%10+'0');
                x/=10;
            }
            reverse(tmp.begin(),tmp.end());
            ans+=tmp;
        }
        return ans;
    }
};