题目链接

LeetCode

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入**：**``nums = [10,2]
输出： "210"

示例 2：

输入**：**``nums = [3,30,34,5,9]
输出： "9534330"

示例 3：

输入**：**nums = [1]
输出： “1”

示例 4：

输入**：**nums = [10]
输出： “10”

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

  解题思路

  自定义排序

  我们通过比较每个数字在前和在后的结果，将数据排序，优化也可以现将数字全部转为字符串，节省一次转换，但是空间复杂度会上升，因为要保存字符串。

  # 第一步：定义比较函数，把最大的放左边
  # 第二步：排序
  # 第三步：返回结果
  def compare(x, y): return int(y+x) - int(x+y)

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        int len = nums.size();
        if(len==0)
            return "";
        sort(nums.begin(),nums.end(),[](const int &x, const int &y){
            string s1 = to_string(x);
            string s2 = to_string(y);
            return s1+s2>s2+s1;
        });
        if(nums[0]==0)
            return "0";
        string res = "";
        for(int i=0;i<len;++i){
            res += to_string(nums[i]);
        }
        return res;
    }
};

// 先转为string
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        if(nums.size()==0)
            return "";
        vector<string> snums;
        for(const int n : nums){
            snums.push_back(to_string(n));
        }
        sort(snums.begin(),snums.end(),[](const string& s1,const string& s2){
            return s1+s2>s2+s1;
        });
        if(snums[0]=="0")
            return "0";
        string res = "";
        for(const string s : snums){
            res += s;
        }
        return res;
    }
};

class Solution {
    public String largestNumber(int[] nums) {
        Integer[] newNums = new Integer[nums.length];
        for(int i = 0; i < nums.length;++i){
            newNums[i] = nums[i];
        }
        Arrays.sort(newNums,(x,y)->{
            long sx = 10, sy = 10;
            // x 的位数
            while(sx <= x){
                sx *= 10;
            }
            // y 的位数
            while(sy <= y){
                sy *= 10;
            }
            // 字符串 y + x 表示的数 大于 字符串 x + y 表示的数时 排序
            return (int)(y * sx + x - x * sy - y);
        });
        if(newNums[0] == 0){
            return "0";
        }
        StringBuilder res = new StringBuilder();
        for(int n : newNums){
            res.append(n);
        }
        return res.toString();
    }
}


// 堆排序

class Solution {
    public String largestNumber(int[] nums) {
        // 堆排序
        Queue<String> pq = new PriorityQueue<>((x,y)->(y+x).compareTo(x+y));
        for(int n : nums){
            pq.offer(String.valueOf(n));
        }
        if(pq.peek().charAt(0) == '0'){
            return "0";
        }
        StringBuilder res = new StringBuilder();
        while(!pq.isEmpty()){
            res.append(pq.poll());
        }
        return res.toString();
    }
}

• 时间复杂度 O(nlog n log m) :其中 n 是给定序列的长度，m 是 32 位整数的最大值，每个数转化为字符串后的长度是 O(logm) 的数量级。排序比较函数的时间复杂度为 O(logm)，共需要进行 O(nlogn) 次比较。同时我们需要对字符串序列进行拼接，时间复杂度为O(nlogm)，在渐进意义上小于 O(nlognlogm)。
• 空间复杂度 O(log n)