Leetcode#179. Largest Number

Posted on | In |

字符串比较的奇巧淫技。

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

Example1:

1
2
Input: [10,2]
Output: "210"

Example2:

1
2
Input: [3,30,34,5,9]
Output: "9534330"

思路很确定就是先比较第一位排序然后第二位排序。下边的这个解法就只用了一次排序，虽然时间复杂度稍微高一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    
    static bool cmp(string& s1, string& s2){
        string c = s1+s2;
        string d = s2+s1;
        return c.compare(d) > 0;
    }
    
    string largestNumber(vector<int>& nums) {
        
        vector<string> strs;
        for(int i = 0; i<nums.size(); i++){
            strs.push_back(to_string(nums[i]));
        }
        
        sort(strs.begin(), strs.end(), cmp);
        string ans = "";
        for(int i = 0; i<strs.size(); i++){
            ans += strs[i];
        }
        
        if(ans[0] == '0') ans = "0"; //边界条件
        return ans;
        
    }
};