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. 最大數