Leetcode 贪心算法之Largest Number

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

实例

示例 1：
输入：nums = [10,2]
输出：“210”

示例 2：
输入：nums = [3,30,34,5,9]
输出：“9534330”

思路分析

利用贪心算法分析，只需要使高位的数字大于低位的数字。
一开始我直接对nums排序，然后用string接受之后直接return，但是发现上面所说的大于不是指数学上的大于，而是对于高位数开始比较的大于。
于是我对sort函数重写了比较函数mycompare，我一开始想利用取余来逐个比较高位数字的大小，再从大到小排序，但数字位数未知，不好操作。
于是我在网上查阅，发现我只要将函数内的两个数用string接收，然后按不同先后拼接这两个数字，这样我只需要比较字符串的大小即可。

代码展示

bool mycompare(int a,int b){
    string a1;
    string a2;
    a1+=to_string(a);
    a2+=to_string(b);
    if((a1+a2)>(a2+a1)){
        return true;
    }
    return false;
}



class Solution {
public:
    string largestNumber(vector<int>& nums) {
        string num;
        sort(nums.begin(),nums.end(),mycompare);
        for(int i=0;i<nums.size();i++){
            num+=to_string(nums[i]);
        }
        if(num[0]=='0') return "0";
        return num;
    }
};

运行结果

跳转原题点here