讨论/题目交流/给一个数字,找出能组成的最大数? 比如123465,组成最大的数654321;/
给一个数字,找出能组成的最大数? 比如123465,组成最大的数654321;

求一道题目的做法:给一个数字,找出能组成的最大数? 比如123465,组成最大的数654321;
这道题,我的想法是:
1、for循环将数字一个个取出,组成数组;
2、将数组排序(或者二分查找到index,插入index)
3、再for循环将数组组成数字;

这样是不是太麻烦了,有没有更好的方法

展开讨论
15.10发起于 2020-03-09
共 4 个讨论

用一个中间数组int[10]记录每个数字的出现次数,通过一次循环计算每个数字的出现次数,然后从大到小一个个累积起来

from collections import Counter

getMax = lambda num: int(''.join(
    i * t 
    for i, t in sorted(
        Counter(str(num)).items(), 
        reverse=True
    )
))

贪心算法可解,计算每两个数拼接起来的数取较大的那种排列情况,这个过程作为 sort 函数的回调,考虑到这题每个数字长度都一样,直接倒序排列即可。

第一步变化成数组看来是必须的,但第二步排序的方法可以优化,因为排序对象都是个位数,所以只需要遍历一遍数组,将每个数字出现的次数统计出来,再生成结果,这样复杂度会降低