LeetCode 179. 最大數(shù)【c++/java詳細(xì)題解】

tuantuan 發(fā)布于2021-09-02 15:15 / 2385人閱讀

摘要：示例輸入輸出示例輸入輸出示例輸入輸出示例輸入輸出思路貪心給定一組非負(fù)數(shù)，重新排列使其組成一個最大的整數(shù)。具體過程如下自定義排序規(guī)則函數(shù)，將數(shù)組按照自定義排序規(guī)則重新排序。時間復(fù)雜度分析排序的時間復(fù)雜度為。

1、題目

給定一組非負(fù)整數(shù) nums，重新排列每個數(shù)的順序（每個數(shù)不可拆分）使之組成一個最大的整數(shù)。

注意:

輸出結(jié)果可能非常大，所以你需要返回一個字符串而不是整數(shù)。

示例 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)$

給定一組非負(fù)數(shù)，重新排列使其組成一個最大的整數(shù)。

樣例：

如樣例所示，[3,30,34,5,9]所能組成的最大數(shù)字是"9534330"，下面來講解貪心的做法。

假設(shè)給定我們包含兩個數(shù)字的數(shù)組[a,b]，如果"ab"組合大于"ba"組合，那么我們優(yōu)先選擇a進(jìn)行拼接。比如nums = [10,2]，"210"組合明顯大于"102"組合，因此我們優(yōu)先選擇2進(jìn)行拼接，這樣我們就自定義了一個排序規(guī)則。

但是擴(kuò)展到一個序列來講，一個序列要能夠正確地自定義排序，需要這種排序規(guī)則滿足全序關(guān)系，即以下三個關(guān)系：

如果 a ≤ b 且 b ≤ a 則 a = b (反對稱性)
如果 a ≤ b 且 b ≤ c 則 a ≤ c (傳遞性)
如果 a ≤ b 或 b ≤ a (完全性)

詳細(xì)證明可看官解。滿足了全序關(guān)系，我們就可以將nums數(shù)組按照自定義排序規(guī)則重新排序，最后返回拼接好的字符串即可。

實(shí)現(xiàn)細(xì)節(jié)：

c++自定義排序，實(shí)現(xiàn)一個cmp函數(shù)。

static bool cmp(int a,int b) //自定義排序規(guī)則    {        string as = to_string(a), bs = to_string(b);        return as + bs > bs + as;    }

java自定義排序，Arrays.sort()結(jié)合lamda表達(dá)式。

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

具體過程如下：

1、自定義排序規(guī)則函數(shù)，將nums數(shù)組按照自定義排序規(guī)則重新排序。
2、從頭到尾遍歷nums數(shù)組，取出nums中的每一個數(shù)，拼接到答案字符串res中。
3、判斷字符串res是否是全0，如果是全0，則返回"0"，否則返回res。

時間復(fù)雜度分析： 排序的時間復(fù)雜度為 $O (n l o g n)$ 。

3、c++代碼

class Solution {public:    static bool cmp(int a,int b) //自定義排序規(guī)則    {        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) -> {  //自定義排序規(guī)則            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();    }}