LeetCode

2015.1.23 20:24

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.

Solution:

　　Sort the numbers and piece them together, you'll get the answer, either largest or smallest. As for how to sort them, please see the comparator().

　　Time complexity is O(n * log(n)), space complexity may be the same, or less.

Accepted code:

 1 //#define ZZ
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8 
 9 bool comparator(const string &s1, const string &s2)
10 {
11     string s12, s21;
12 
13     s12 = s1 + s2;
14     s21 = s2 + s1;
15 
16     bool res = s12 < s21;
17     s12.clear();
18     s21.clear();
19 
20     return res;
21 }
22 
23 class Solution {
24 public:
25     string largestNumber(vector<int> &num) {
26         char s[100];
27         vector<string>vs;
28 
29         int n, i;
30 
31         n = (int)num.size();
32         for (i = 0; i < n; ++i) {
33             sprintf(s, "%d", num[i]);
34             vs.push_back(string(s));
35         }
36 
37         sort(vs.begin(), vs.end(), comparator);
38         string res = "";
39 
40         for (i = n - 1; i >= 0; --i) {
41             res += vs[i];
42         }
43         vs.clear();
44 
45         i = 0;
46         n = (int)res.length();
47         while (i < n - 1 && res[i] == '0') {
48             ++i;
49         }
50         res = res.substr(i, n - i);
51 
52         return res;
53     }
54 };
55 
56 #ifdef ZZ
57 int main()
58 {
59     vector<int> num;
60     int n;
61     int i;
62     Solution sol;
63 
64     while (cin >> n) {
65         num.resize(n);
66         for (i = 0; i < n; ++i) {
67             cin >> num[i];
68         }
69         cout << sol.largestNumber(num) << endl;
70         num.clear();
71     }
72 
73     return 0;
74 }
75 #endif