最大数 (lintcode:largest-number)

给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。最后的结果可能很大，所以我们返回一个字符串来代替这个整数。
样例：
给出 [1, 20, 23, 4, 8]，返回组合最大的整数应为8423201。

思路：
把两个数拼在一起，然后再把这两个数换个顺序再拼在一起，这时候就可以直接比较了。比如2332和23，变成233223和232332两个数，这时候哪个数更大，就说明这个数前半部分的那个数是更大的，这里是2332。

我的第一种方法

def largestNumber(nums):
    str_nums = map(str, nums)
    for i in xrange(len(nums)):
        for j in xrange(i+1, len(nums)):
            int_ij = int(str_nums[i] + str_nums[j])
            int_ji = int(str_nums[j] + str_nums[i])
            if int_ij < int_ji:
                str_nums[i], str_nums[j] = str_nums[j], str_nums[i]
    if str_nums[0] == '0':
        return '0'
    return ''.join(str_nums)

我的第二种方法：

def ab(a, b):
    longab = long(a+b)
    longba = long(b+a)
    if longab > longba:
        return -1
    elif longab < longba:
        return 1
    else:
        return 0

def largestNumber(nums):
    str_nums = map(str, nums)
    str_nums2 = sorted(str_nums, cmp=ab)
    if str_nums2[0] == '0':
        return '0'
    return ''.join(str_nums2)

sorted()函数，对可迭代的对象进行排序操作。
语法：sorted(iterable, cmp, key, reverse)
返回值：列表
参数：
iterable 可迭代对象
key 用来比较的元素。用一个函数来指定可迭代对象中的一个元素来进行排序。函数只有一个参数。默认值为可迭代对象中的第一个元素。
reverse 排序规则，默认 reverse = False 升序，若指定 reverse = True 则为降序。

重点说说 cmp：
cmp 用于比较的函数。

a = [1,2]

def ab(a,b):
  #函数体
  
print sorted(a, cmp=ab)

#如果想2排在1后面，即升序:
def ab(a,b):
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0
        
#如果想2排在1前面，即降序：
def ab(a,b):
    if a < b:
        return 1
    elif a > b:
        return -1
    else:
        return 0
      
#其实返回值为”大于零“、”小于零“、”等于零“就行，所以可以简化为
#升序
def ab(a,b):
    return a - b

网上找到最简洁的代码：

def compare(a, b):
    return [1, -1][a + b > b + a]

def largestNumber(nums):
    nums = sorted([str(x) for x in nums], cmp = compare)
    ans = ''.join(nums).lstrip('0')
    return ans or '0'

lintcode 原题
思路的出处
最简代码的出处

20180110

最后编辑于：2018.01.29 11:13:56