leetcode_[python/C++] 179. Largest Number(數字組合成最大數）

題目連結

【題目】

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

【分析】

剛開始看到這道題是不是要好幾個循環呀，後來想了想這不就是到排序題麼，雖然很像是組合題，但其實隻要改寫下排序函數，進而對nums進行排序就可以了

變成string進行排序

比如 12 13

則排序”12” “13”

“12”+”13” = “1213”

“13”+”12” = “1312”

我們要的是”1312”>”1213”

排序函數需要注意就是

return a>b

or return a-b

這兩個是不一樣的

比如在C++ 的qsort中用到的是return a-b的做法

在一些map,set什麼的用到的是return a>b的做法

而且：

return a-b 是從小到大

return b-a 是從大到小

return a>b 是從大到小

return b>a 是從小到大

可以看下下面這個連結淺談C/C++排序函數中cmp()比較函數的寫法

首先看下python的寫法：

class Solution:
    # @param {integer[]} nums
    # @return {string}
    def largestNumber(self, nums):
        comp = lambda a,b: if a+b>b+a else -
        num_to_str = map(str,nums)
        num_to_str.sort(cmp = comp,reverse = True)
        # num_to_str.sort(cmp = lambda a,b:-1 if a+b<b+a else 0,reverse = True) #慢
        # num_to_str.sort(cmp = lambda a,b:cmp(b+a,a+b),reverse = True) #not cmp(a+b,b+a)
        #return str(int(''.join(num_to_str)))
        return '0' if num_to_str[] == '0' else ''.join(num_to_str)
           

上面注釋的寫法讀者可以自行檢驗，都是可以AC的寫法

接着讀者可以試一下把上面的comp函數改寫下面這幾種寫法，然後自行意會

comp = lambda a,b: if a+b>b+a else -  true
comp = lambda a,b:- if a+b<b+a else   true
comp = lambda a,b: if a+b>b+a else -  true
comp = lambda a,b: if a+b>b+a else    false
           

是以其實可以寫成一行

return str(int("".join(sorted([str(x) for x in nums], cmp = lambda a, b: int(b + a) - int(a + b)))))
           

C++

在C++中同樣可以像python那樣的寫法，在discuss上看到的

class Solution {
public:
    string largestNumber(vector<int>& nums) {
       sort(nums.begin(), nums.end(), [](int a, int b){ return to_string(a) + to_string(b) > to_string(b) + to_string(a);});
       string ans = accumulate(nums.begin(), nums.end(), string(), [](string &r, int a){return r + to_string(a);});
       return ans[] == '0' ? "0" : ans;
       }
};
           

反正我是不會寫這種

但其實這樣的效率比我自己寫的好像好差一點的

class Solution {
public:
static bool compare(string a, string b){
    return a+b<b+a; 
}
string largestNumber(vector<int>& nums) {
    if (nums.empty()) return "";
    vector<string> num_str;
    for (int i=;i<nums.size();i++){
        num_str.push_back(to_string(nums[i]));
    }
    sort(num_str.begin(),num_str.end(),compare);
    string res="";
    for (int i=nums.size()-;i>=;i--){
        res+=num_str[i];
    }
    if (compare("0",res)) return res;
    else return "0";
}
};