问题描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解题思路

设十进制数 A，B 的位数分别为 a，b；比较规则为：

比如：10 的位数是 2，9 的位数是 1，且 9 * 102 + 10 > 10 * 101 + 9，所以 9 > 10

设序列 [A, B, D, E] 是遵守上面的比较规则的降序序列，元素的位数分别为 a、b、d、e，则如下三个不等式成立：

  1. A * 10b + B >= B * 10a + A <===> A * 10b - B * 10a >= A - B
  2. A * 10d + D >= D * 10a + A <===> A * 10d - D * 10a >= A - D
  3. B * 10d + D >= D * 10b + B <===> B * 10d - D * 10b >= B - D

由该序列中的元素组成的数为：A * 10b + d + e + B * 10d + e + D * 10e + E，将其记为 n1。

将 A 与序列中的任意一个元素互换，会得到一个新序列，下面以 A 与 D 进行互换为例进行说明，互换后的序列中的元素组成的数为：D * 10a + b + e + B * 10a + e + A * 10e + E，将其记为 n2。

则:

n1 - n2 = A * 10b + d + e - D * 10a + b + e + B * 10d + e - B * 10a + e + D * 10e - A * 10e

n1 - n2 = 10b + e * (A * 10d - D * 10a) + B * 10d + e - B * 10a + e + D * 10e - A * 10e

带入不等式 2，得到：

n1 - n2 >= A * 10b + e - D * 10b + e + B * 10d + e - B * 10a + e + D * 10e - A * 10e

n1 - n2 >= (A * 10b + e - B * 10a + e) + (B * 10d + e - D * 10b + e) + D * 10e - A * 10e

n1 - n2 >= 10e * (A * 10b - B * 10a) + 10e * (B * 10d - D * 10b) + 10e * (D - A)

带入不等式 1、3，得到：

n1 - n2 >= 10e * (A - B) + 10e * (B - D) + 10e * (D - A) = 0

所以 n1 >= n2。

综上可以得出：把遵守本文定义的比较规则的有序序列中较大的数与任意较小的数互换后得到的序列组成的数不大于互换前的序列组成的数。

上面证明了 A 与 D 互换的场景，对于更复杂的场景可以分步证明，比如证明 [D, B, E, A] 组成的数不大于 [A, B, D, E] 组成的数的步骤是：

  1. [A, B, D, E] 组成的数不小于 [D, B, A, E] 组成的数
  2. [D, B, A, E] 组成的数不小于 [D, B, E, A] 组成的数

Python 实现

class Solution(object):
    class Number(object):
        def __init__(self, number):
            assert number >= 0
            self.digit_number = self.get_digit_number(number)
            self.number = number

        @staticmethod
        def get_digit_number(number):
            if number == 0:
                return 1

            digit_number = 0
            while number > 0:
                digit_number = digit_number + 1
                number = number / 10
            return digit_number

        def __cmp__(self, other):
            if not isinstance(other, self.__class__):
                raise TypeError()

            n1 = self.number * (10 ** other.digit_number) + other.number
            n2 = other.number * (10 ** self.digit_number) + self.number

            if n1 > n2:
                return 1
            elif n1 < n2:
                return -1
            return 0

        def __str__(self):
            return str(self.number)

        def __repr__(self):
            return str(self.number)

    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if all(number == 0 for number in nums):
            return "0"

        nums = sorted([self.Number(number) for number in nums], reverse=True)
        return "".join([str(number) for number in nums])