Leetcode.179.Largest Number
2019-11-19 本文已影响0人
Jimmy木
题目
给定一个整型数组, 求出用这些数字能组成的最大数字.
Input: [10, 2]
Output: "210"
Input: [3,30,34,5,9]
Output: "9534330"
Input: [8247, 824]
Output: "8248247"
Input: [12,121]
Output: "12121"
思路
利用快速排序, 修改判断数字大小的规则. 判断两个数大小, 可以将两个数字长度变得相等就会比较容易.
bool isBigger(int a, int b) {
string aa = to_string(a) + to_string(b);
string bb = to_string(b) + to_string(a);
for (int i = 0; i < aa.size(); i++) {
if (aa[i] == bb[i]) {
continue;
}
return aa[i] > bb[i];
}
return false;
}
void largestNumberHelper(vector<int>& nums, int l, int r) {
if (l < r) {
int i = l, j = r, x = nums[l];
while (i < j) {
while (i < j && isBigger(x,nums[j])) j--;
if (i < j) nums[i++] = nums[j];
while (i < j && isBigger(nums[i], x)) i++;
if (i < j) nums[j--] = nums[i];
}
nums[i] = x;
largestNumberHelper(nums, l, i-1);
largestNumberHelper(nums, i+1, r);
}
}
string largestNumber(vector<int>& nums) {
vector<int> vec(10,0);
int n = (int)nums.size();
largestNumberHelper(nums, 0, n-1);
if (nums[0] == 0) {
return "0";
}
string res;
for (int num : nums) {
res += to_string(num);
}
return res;
}
总结
这题关键在于排序和比较两个数字大小. 其实是比较字符串的大小, 考虑到整数越界, 最好将两个字符串加起来变得相等.