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

问题：给定一个数组，求将数组元素拼凑成一个值最大的整数。

将整型数组的转化为字符串数组，用 std::sort 对字符串数组排序，使得排序后元素直接连接成为最大值整数。

使用默认的比较函数排序，会得到不一定是最大值，例如 {360, 36} 排序后得到的是 36036 ，明显不是小于 36360。解决这个问题，就是重写比较函数，使得排序后的两个元素连接成为较大的整数即可，很简洁。

 1     int static comp(string s1, string s2){
 2         return (s1 + s2) > (s2 + s1);
 3     }
 4     
 5     string largestNumber(vector<int>& nums) {
 6         vector<string> numsStr;
 7         for (int i = 0 ; i < nums.size(); i++) {
 8             numsStr.push_back(to_string(nums[i]));
 9         }
10         
11         std::sort(numsStr.begin(), numsStr.end(), comp);
12     
13         string res = "";
14         for (int i = 0 ; i < numsStr.size(); i++) {
15             res += numsStr[i];
16         }
17         
18         int i = 0;
19         while (i < res.size()-1 && res[i] == '0') {
20             i++;
21         }
22         res = res.substr(i);
23         
24         return res;
25     }

[LeetCode] 179. Largest Number 解题思路

相关推荐