首页 > 代码库 > [LeetCode] Largest Number

[LeetCode] 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.

 

老题了,主要是搞懂cmp函数,前置0的处理还有待优化,不用copy两遍字符串。

 1 bool cmp(const string s1, const string s2) { 2     return (s1 + s2) > (s2 + s1); 3 } 4  5 class Solution { 6 public: 7     string largestNumber(vector<int> &num) { 8         vector<string> s_num(num.size()); 9         stringstream stream;10         for (int i = 0; i < num.size(); ++i) {11             stream << num[i];12             stream >> s_num[i];13             stream.clear();14         }15         sort(s_num.begin(), s_num.end(), cmp);16         string tmp_res;17         for (int i = 0; i < s_num.size(); ++i) {18             tmp_res += s_num[i];19         }20         string res;21         bool flag = false;22         for (int i = 0; i < tmp_res.size(); ++i) {23             if (tmp_res[i] != 0) {24                 res.push_back(tmp_res[i]);25                 flag = true;26             } else if (flag) {27                 res.push_back(tmp_res[i]);28             }29         }30         if (!flag) res.push_back(0);31         return res;32     }33 };

 

[LeetCode] Largest Number