题目描述

给一数组的数（可能有多位，即有些数>= 10），问他们能排列组合成的最大数字。(在不分割位上的数字的情况下的意思)

算法1

(库函数sort) $O(n)$

附带lambda表达式用法，
还有使用funstool来实现旧版Python的cmp功能

时间复杂度

参考文献

Python3 代码

def largestNumber(self, nums: List[int]) -> str:
        comp=lambda a,b:1 if a+b>b+a else -1 if a+b<b+a else 0
        num = list(map(str, nums))
        num.sort(key=functools.cmp_to_key(comp),reverse=True)
        return str(int("".join(num)))

注：这里a + b 是两个字符项合并，而不是数值相加，如："2" + "10"结果是"210"

高端Python写法（实际没啥用，对于普通人来说很难维护） 注：python3里没cmp 还是得用上述functools

return "".join(sorted(map(str, nums), cmp=lambda n1, n2: -1 if n1+n2>n2+n1 else (1 if n1+n2<n2+n1 else 0)))

P3

if not any(nums): return "0"
    return "".join(sorted(map(str, nums), key=functools.cmp_to_key(lambda n1, n2: -1 if n1+n2>n2+n1 else (1 if n1+n2<n2+n1 else 0))))

其他各式各样算法

# bubble sort
def largestNumber2(self, nums):
    for i in range(len(nums), 0, -1):
        for j in range(i-1):
            if not self.compare(nums[j], nums[j+1]):
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return str(int("".join(map(str, nums))))

def compare(self, n1, n2):
    return str(n1) + str(n2) > str(n2) + str(n1)

# selection sort
def largestNumber3(self, nums):
    for i in range(len(nums), 0, -1):
        tmp = 0
        for j in range(i):
            if not self.compare(nums[j], nums[tmp]):
                tmp = j
        nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
    return str(int("".join(map(str, nums))))

# insertion sort
def largestNumber4(self, nums):
    for i in range(len(nums)):
        pos, cur = i, nums[i]
        while pos > 0 and not self.compare(nums[pos-1], cur):
            nums[pos] = nums[pos-1]  # move one-step forward
            pos -= 1
        nums[pos] = cur
    return str(int("".join(map(str, nums))))

# merge sort        
def largestNumber5(self, nums):
    nums = self.mergeSort(nums, 0, len(nums)-1)
    return str(int("".join(map(str, nums))))

def mergeSort(self, nums, l, r):
    if l > r:
        return 
    if l == r:
        return [nums[l]]
    mid = l + (r-l)//2
    left = self.mergeSort(nums, l, mid)
    right = self.mergeSort(nums, mid+1, r)
    return self.merge(left, right)

def merge(self, l1, l2):
    res, i, j = [], 0, 0
    while i < len(l1) and j < len(l2):
        if not self.compare(l1[i], l2[j]):
            res.append(l2[j])
            j += 1
        else:
            res.append(l1[i])
            i += 1
    res.extend(l1[i:] or l2[j:])
    return res

# quick sort, in-place
def largestNumber(self, nums):
    self.quickSort(nums, 0, len(nums)-1)
    return str(int("".join(map(str, nums)))) 

def quickSort(self, nums, l, r):
    if l >= r:
        return 
    pos = self.partition(nums, l, r)
    self.quickSort(nums, l, pos-1)
    self.quickSort(nums, pos+1, r)

def partition(self, nums, l, r):
    low = l
    while l < r:
        if self.compare(nums[l], nums[r]):
            nums[l], nums[low] = nums[low], nums[l]
            low += 1
        l += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low