179. Largest Number

發表於 | 分類於

problem

solution

bucket sort

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:
    string largestNumber(vector<int>& nums) {
        // bucket sort
        vector<vector<string>> bucket(10);
        for(int n :nums){
            string s = to_string(n);
            int c = s[0] -'0';
            bucket[c].push_back(s);
        }
        for(int i = 0 ;i<=9;++i){
            sort(bucket[i].begin(), bucket[i].end(), [](string a, string b){
               return a+b > b+a; 
            });
        }
        
        string ret;
        for(int i=9;i>-1;--i){
            for(string v:bucket[i]) ret += v;
        }
        int l=0;
        while(l<ret.size() && ret[l]=='0') l++;
        string ans = ret.substr(l);
        return ans.empty()?"0":ans;
        
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(n)