【每日一题0705】最大数

给定一个list 由一些非负整数组成 ,重新排列他们的顺序把他们组成一个最大的整数。

例子:

输入:
[30,1]
返回值:
“301”

def fn(s):
   pass
assert fn([30,1]) == "301"
assert fn([1, 201, 20, 9, 8]) == "98202011"
assert fn([1, 203, 20, 9, 8]) == "98203201"

备注:需要保证列表里面的每个元素不被拆开
因重新组合的整数可能较大,将整数变为字符串后返回

题目来源:最大数_牛客题霸_牛客网

import itertools
def fn(list):
    ls = []
    for p in itertools.permutations(list):
        a = ''
        for x in p:
           a = a + str(x)
        ls.append(int(a))
    print(str(max(ls)))
    return str(max(ls))
assert fn([30,1]) == "301"
assert fn([1, 201, 20, 9, 8]) == "98202011"
assert fn([1, 203, 20, 9, 8]) == "98203201"

这个狠,还有这么个方法

排列组合有点耗性能呀…会出现一些不必要的组合数据,数据量一大会存在问题.

题解1:两次排序

def fn(nums):
    
    # 根据首位先排序
    s = list(map(str, nums))
    ordered = sorted(s, key=lambda x:str(x), reverse=True)
    
    # 首位相同的,进行二次排序
    for i in range(len(ordered)-1):
        if ordered[i][0] == ordered[i+1][0]:
            if int(ordered[i][-1]) < int(ordered[i+1][0]):
                ordered[i], ordered[i+1] = ordered[i+1], ordered[i]

    return ''.join(ordered)

assert fn([30,1]) == "301"
assert fn([1, 201, 20, 9, 8]) == "98202011"
assert fn([1, 203, 20, 9, 8]) == "98203201"

题解2:穷举

import itertools

def fn(nums):
    pertmute = list(itertools.permutations([str(x) for x in nums], len(nums)))
    result = list(map(lambda x:''.join(x), pertmute))
    return max(result)

assert fn([30,1]) == "301"
assert fn([1, 201, 20, 9, 8]) == "98202011"
assert fn([1, 203, 20, 9, 8]) == "98203201"

题解3:分治

import itertools

def fn(nums):
    total = []
    for i in range(10)[::-1]:
        data = list(filter(lambda x:str(x).startswith(str(i)), nums))
        if data:
            if len(data) > 1:
                p = list(itertools.permutations(data, len(data)))
                total.append([max([str(x)+str(y) for x,y in p])])
            else:
                total.append(data)

    return ''.join([str(x[0]) for x in total])

assert fn([30,1]) == "301"
assert fn([1, 201, 20, 9, 8]) == "98202011"
assert fn([1, 203, 20, 9, 8]) == "98203201"

:partying_face: :partying_face: :partying_face: :partying_face: :partying_face: :partying_face:

1 Like
关闭