LeetCode 179——最大数(排序)

标签: LeetCode刷题

一、题目介绍

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

       需要将传入的数组,按照指定的规则进行排序,最后再将排序数组中的元素从头到尾,添加到一个字符串中返回。本题难点在于自己定义排序规则。降序排序规则如下:

(1)当两个数的高位不同,高位大的数排在前面。

(2)当两个数的高位相同,且位数相同时,从左到右比较每一位的数,大的排在前面。比如[30,34],排序后为[34,30]。

(3)当两个数的高位相同,且位数不同时,如[32, 321],对于321而言,32后面的每一位都需要大于32的首位3,才能排到前面排序后为[32,321]。如果[32, 324],排序后为[324,32]。

(4)当两个数的高位相同,且位数不同时,如[12,121],当按照(3)的规则无法判断,因为121后面的1,与12的首位1相同,这时需要比较12的末尾2,与121的末尾1之间的大小关系。因此排序后为[12,121]。

(5)需要考虑,所有元素均相同的情况。

(6)需要考虑,输出的字符串不能为“01”,“00”之类的结果。

三、解题代码

bool comp(const int& a, const int& b)
{
    string ls = to_string(a);
    string rs = to_string(b);
    int ln = ls.size();
    int rn = rs.size();
    char lc, rc;
    for(int i = 0; i < ln || i < rn; ++i)
    {
        if(i < ln)
            lc = ls[i]; //取某一位数
        else
            lc = ls[0]; //ls为rs的前缀,将当前字符赋值为ls的首位字符
        if(i < rn)
            rc = rs[i];
        else
            rc = rs[0]; //rs为ls的前缀
        if(lc == rc)
            continue;
        else
            return lc > rc;
    }
    if(ls[ln-1] != rs[rn-1])  //如121和12的情况,需要比较两个字符串的末尾字符
        return ls[ln-1] > rs[rn-1];
    return false; //全都相等的情况
}
class Solution {
public:    
    string largestNumber(vector<int>& nums) {
        int n = nums.size();
        string res;
        if(n == 0)
            return res;
        sort(nums.begin(), nums.end(), comp);
        for(int i = 0; i < n; ++i)
        {
            if(nums[0] == 0) //避免数字的最前面为0
            {
                res = "0";
                break;
            }
            res += to_string(nums[i]);
        }
        return res;
    }
};

四、解题结果

版权声明:本文为qq_39661206原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39661206/article/details/103530833