本节通过解决一个经典的最大整数拼接问题,说明盲目贪心算法策略是无法求得全局最优解的.

问题描述:

给定一个列表,其中包括一些非负整数,试求如何组合这些非负整数,才能组成一个最大整数,为了避免最大整数过大造成溢出,返回结果为字符类型.

思路解析:

初遇这个问题,可能会直观的认为只要将值较大的数字放在整数前面,较小的数字放在整数后面即可,但只要经过简单的验证就可以知道这一想法是错误的.例如输入列表为[121,12],若将值较大的元素放在前面,最终结果得到为12112,若将较小值放在前面,那么整数就是12121,显然12121大于12112,可以直接推翻这个贪心策略.

由此可见在决定两个元素如何拼接时,不能简单的通过两元素大小进行判断,需要对比二者不同拼接方式所组成的数字大小才能决定,因此可以使用双层循环,遍历数组的每两个元素组合,每次循环分别确定拼接的第一位,第二位.....然后将元素按照顺序拼起来返回即可.变量定义如下:

nums变量:表示给定的,由非负整数构成的列表

temp变量:表示对nums进行排序过程中的中间变量

完整代码如下:

def largestNumber(nums):
    # 将数组中的每个整数转换成字符串
    nums = [str(i) for i in nums]
    
    # 两层循环，用于比较所有字符串拼接后的数值大小
    for i in range(len(nums)-1):
        for j in range(i+1,len(nums)):
            # 如果当前字符串i和字符串j拼接后的数值小于字符串j和字符串i拼接后的数值
            # 则交换字符串i和字符串j的位置
            if int(nums[i]+nums[j])<int(nums[j]+nums[i]):
                temp = nums[i]
                nums[i]=nums[j]
                nums[j]=temp
    
    # 将排序后的字符串数组拼接成一个字符串
    largest_num = ''.join(nums)
    
    # 如果拼接后的字符串表示的数字是0，则直接返回0
    if int(largest_num)==0:
        return str(0)
    else:
        # 否则返回拼接后的字符串
        return largest_num