备战蓝桥杯Day28 - 拼接最大数字问题

问题描述

有n个非负整数，将其按照字符串拼接的方式拼接为一个整数如何拼接可以使得得到的整数最大?

例: 32,94,128,1286,6,71可以拼接除的最大整数为 94716321286128。

问题思路

1.比较两个字符串的第一个数字，数值大的在前面，数值小的在后面

2.当两个字符串长度差不多且其中一个是另一个的字串时，从第一个数字开始比较两个字符串的方法就不太可行了。

3.更好的解决办法是：比较两个字符串结合在一起后的字符串的大小，比如：“128” + ”1286“ < "1286" + "128",通过比较字符串拼接后的数值大小，我们的算法也更容易实现。

代码实现

比较大小是调用python自带的包，也可以自己写冒泡排序来进行排序。

from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]


def xy_cmp(x, y):  # 定义两个字符串拼接后数值比较函数
    if x+y < y+x:
        return 1  
    elif x+y > y+x:
        return -1
    else:
        return 0


def num_join(li):  # 定义拼接函数
    li = list(map(str, li))  # 通过map函数将列表中的数字都转换成字符串格式
    li.sort(key=cmp_to_key(xy_cmp))
    return "".join(li)

print(num_join(li))

冒泡排序的实现我再想想。

一步一步的大踏步向前吧！