2.1 数组排成最小数

1 把数组排成最小数

问题描述

• 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

• 示例 1:

  • 输入: [10,2]
  • 输出: “102”

• 示例 2:

  • 输入: [3,30,34,5,9]
  • 输出: “3033459”

链接

问题分析

问题分类

• 排序

算法设计

• 算法原理：此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums 中任意两数字的字符串为 x 和 y ，则规定 排序判断规则 为：

  • 若拼接字符串 x+y>y+x ，则 x “大于” y ；
  • 反之，若 x+y<y+x ，则 x “小于” y ；

• 算法流程

  • 初始化： 字符串列表 strsstrs ，保存各数字的字符串格式；
  • 列表排序： 应用以上 “排序判断规则” ，对 strsstrs 执行排序；
  • 返回值： 拼接 strsstrs 中的所有字符串，并返回。

算法分析

• 时间复杂度O(NlogN) ： N 为最终返回值的字符数量（ strs列表的长度 N≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2)
• 空间复杂度 O(N)O(N) ： 字符串列表 strsstrs 占用线性大小的额外空间。

算法实现

• 以下是自己的方法，循环比较

string minNumber(vector<int>& nums) {
    vector<string> vec;
    for(auto a:nums){
        vec.push_back(to_string(a));
    }
    // 太他妈的秀了。这个循环比较。我是服了。
    // 对compare函数有了更深的理解。return true表示第一个参数需要移到第二个参数前。
    // return false。表示第一个参数不需要移到第二个参数前。
    // 也就是说，默认情况下，第一个参数在第二个参数后边。true表示需要移动。false表示不需要移动。
    // 还是官方英文的参考文档说的比较明白
    sort(vec.begin(),vec.end(),[](const string&a,const string&b){
        int i=0,j=0,k=0;
        // return false;
        // 完全相等的情况
        if(a==b)return false;
        // cout<<a<<" "<<b<<endl;
        while(true){
            k++;
            if(k>2*a.size()&&k>2*b.size())return false;
            // cout<<i<<" "<<j<<endl;
            if(a[i]<b[j])return true;
            else if(a[i]>b[j])return false;
            else if(a[i]==b[j]){
                i=(i+1)%a.size();
                j=(j+1)%b.size();
            }
        }           
    });
    string result;
    for(auto s:vec){
        result+=s;
    }
    return result;
}

• 一下是官方的方法。手写快排

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        for(int i = 0; i < nums.size(); i++)
            strs.push_back(to_string(nums[i]));
        quickSort(strs, 0, strs.size() - 1);
        string res;
        for(string s : strs)
            res.append(s);
        return res;
    }
private:
    void quickSort(vector<string>& strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        while(i < j) {
            while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
            while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
            swap(strs[i], strs[j]);
        }
        swap(strs[i], strs[l]);
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
};

• 一下是官方的方法，内置函数

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(int i = 0; i < nums.size(); i++)
            strs.push_back(to_string(nums[i]));
        sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });
        for(int i = 0; i < strs.size(); i++)
            res.append(strs[i]);
        return res;
    }
};