Leetcode.179.Largest Number

题目

给定一个整型数组, 求出用这些数字能组成的最大数字.

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;
}

总结

这题关键在于排序和比较两个数字大小. 其实是比较字符串的大小, 考虑到整数越界, 最好将两个字符串加起来变得相等.