LeetCode 179. 最大数【c++/java详细题解】

目录

• • • 1、题目
    • 2、思路
    • 3、c++代码
    • 4、java代码

1、题目

给定一组非负整数

nums

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

注意:

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

示例 1:

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

示例 2：

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

示例 3：

输入：nums = [1]
输出："1"
           

示例 4：

输入：nums = [10]
输出："10"
           

2、思路

(贪心) O ( n l o g n ) O(nlogn) O(nlogn)

给定一组非负数，重新排列使其组成一个最大的整数。

样例：

如样例所示，

[3,30,34,5,9]

所能组成的最大数字是

"9534330"

，下面来讲解贪心的做法。

假设给定我们包含两个数字的数组

[a,b]

，如果

"ab"

组合大于

"ba"

组合，那么我们优先选择

a

进行拼接。比如

nums = [10,2]

，

"210"

组合明显大于

"102"

组合，因此我们优先选择

2

进行拼接，这样我们就自定义了一个排序规则。

但是扩展到一个序列来讲，一个序列要能够正确地自定义排序，需要这种排序规则满足全序关系，即以下三个关系：

• 如果

  a ≤ b

  且

  b ≤ a

  则

  a = b

  (反对称性)
• 如果

  a ≤ b

  且

  b ≤ c

  则

  a ≤ c

  (传递性)
• 如果

  a ≤ b

  或

  b ≤ a

  (完全性)

详细证明可看官解。 满足了全序关系，我们就可以将

nums

数组按照自定义排序规则重新排序，最后返回拼接好的字符串即可。

实现细节：

c++自定义排序，实现一个

cmp

函数。

static bool cmp(int a,int b) //自定义排序规则
    {
        string as = to_string(a), bs = to_string(b);
        return as + bs > bs + as;
    }
           

java自定义排序，

Arrays.sort()

结合

lamda

表达式。

Arrays.sort(s, (a, b) -> {
            String x = a + b, y = b + a ;
            return y.compareTo(x);
 });  
           

具体过程如下：

• 1、自定义排序规则函数，将

  nums

  数组按照自定义排序规则重新排序。
• 2、从头到尾遍历

  nums

  数组，取出

  nums

  中的每一个数，拼接到答案字符串

  res

  中。
• 3、判断字符串

  res

  是否是全 ，如果是全 ，则返回

  "0"

  ，否则返回

  res

  。

时间复杂度分析： 排序的时间复杂度 为 O ( n l o g n ) O(nlogn) O(nlogn) 。

3、c++代码

class Solution {
public:
    static bool cmp(int a,int b) //自定义排序规则
    {
        string as = to_string(a), bs = to_string(b);
        return as + bs > bs + as;
    }
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for(auto x : nums) res += to_string(x);
        if(res[0] == '0') return "0"; //判断是否是全0
        return res;
    }
};
           

4、java代码

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++) s[i] = nums[i] + "";
        Arrays.sort(s, (a, b) -> {  //自定义排序规则
            String x = a + b, y = b + a ;
            return y.compareTo(x);
        });    
        StringBuilder res = new StringBuilder();
        for (String x : s) res.append(x);
    	if(res.charAt(0) == '0') return "0"; //判断是否是全0
        return res.toString();
    }
}
           

原题链接： 179. 最大数