LeetCode如何把数组排成最小的数

问题背景

给定一个非负整数数组 nums，把数组中所有的元素拼接起来排成一个数，返回能够得到的最小的数。

解题思路

要将数组排成最小的数，就需要确定数组元素之间的相对顺序。首先，我们可以将数组中的元素转换为字符串，然后根据字符串的大小关系进行排序。但是，我们不能直接按照字符串的字典序进行排序，因为这样得到的可能不是最小的数。例如，对于输入 [30,1,3]，按照字典序排序得到的是 [1,3,30]，但是这不是一个最小的数，因为它的拼接结果是 13030，而正确的答案应该是 1303。

所以，我们需要自定义一种排序规则：

1. 将数组中所有元素转换为字符串。
2. 对字符串数组进行排序，排序规则是对于任意两个字符串 s1 和 s2，如果 s1 + s2 < s2 + s1，则 s1 应该排在 s2 的前面，否则 s1 应该排在 s2 的后面。
3. 将排序后的字符串数组拼接起来，即为所求的最小的数。

算法实现

def minNumber(nums):
    # 将数值列表转换为字符串列表
    nums = [str(x) for x in nums]

    # 自定义排序规则
    def compare(x, y):
        if x + y > y + x:
            return 1
        elif x + y < y + x:
            return -1
        else:
            return 0

    # 使用自定义排序规则对字符串列表进行排序
    nums.sort(key=compare)

    # 拼接排序后的字符串列表
    return ''.join(nums)

以上代码实现了将给定数组 nums 排成最小的数的功能。首先，我们使用列表推导式将数值列表转换为字符串列表。然后，定义了一个自定义的排序规则 compare(x, y)。在排序规则中，我们比较两个字符串 s1 和 s2 的拼接结果 s1 + s2 和 s2 + s1 的大小，如果 s1 + s2 < s2 + s1，则认为 s1 应该排在 s2 的前面，如果 s1 + s2 > s2 + s1，则认为 s1 应该排在 s2 的后面，如果 s1 + s2 == s2 + s1，则认为 s1 和 s2 的顺序无所谓。最后，使用 sorted 函数对字符串列表进行排序，排序函数传入自定义的排序规则 compare。最后，使用 join 方法将排序后的字符串列表拼接起来，得到最小的数。

算法分析

时间复杂度：假设数组中有 n 个元素，转换为字符串的时间复杂度是 O(n)，排序的时间复杂度是 O(nlogn)，拼接字符串的时间复杂度是 O(n)，因此总的时间复杂度是 O(nlogn)。

空间复杂度：空间复杂度取决于转换后的字符串数组，所以是 O(n)。