题目链接

牛客网

题目描述

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

解题思路

可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。

class Solution {
public:
    string minNumber(vector<int>& nums) {
       vector<string> strs;
       string ans;
       for(int i=0;i<nums.size();i++){
           strs.push_back(to_string(nums[i]));//转为string
       }
       sort(strs.begin(),strs.end(),[](string &s1,string &s2 ){
           return s1+s2 < s2+s1;
       });// 匿名lambda表达式，自定义排序规则
          // s1+s2 < s2+s1时 s1在s2前面
       for(int i=0;i<strs.size();i++){
           ans+=strs[i];
       }
       return ans;
    }
};
// sort排序如下：
for(int i = 0; i < numbers.length; i++){
    for(int j = i + 1; j < numbers.length; j++){
        pre = numbers[i] + "" +  numbers[j];    //转换成字符串的形式
        last = numbers[j] + "" +  numbers[i];
        if(pre.compareTo(last) > 0){    //比较组合之后的ab和ba
            temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }
    sb.append(numbers[i]);
}

class Solution {
    public String minNumber(int[] nums) {
        Integer[] newNums = new Integer[nums.length];
        for(int i = 0; i < nums.length; ++i){
            newNums[i] = nums[i];
        }
        List<Integer> lst = Arrays.asList(newNums);
        Collections.sort(lst,(o1,o2)->{
            String x = String.valueOf(o1);
            String y = String.valueOf(o2);
            return (x+y).compareTo(y+x);
        });
        Iterator<Integer> it = lst.iterator();
        StringBuilder sb = new StringBuilder();
        while(it.hasNext()){
            sb.append(it.next());
        }
        return sb.toString();
    }
}

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