剑指Offer题解 - Day35

「剑指 Offer 45. 把数组排成最小的数」

力扣题目链接[1]

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

「示例 1:」

输入:[10,2]输出: "102"

「示例 2:」

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

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路：

由题目描述可知，本题是考查排序。要返回拼接数字是最小，那就意味着如果两个数字比较大小，会符合以下结论：

• 首先需要将两个数字拼接为字符串进行比较
• x + y > y + x，那么x大于y
• x + y < y + x，那么x小于y

根据上面的结论，我们可以通过排序来得到最终的结果。

首先想到的是直接使用数组中内置的sort函数来排序。解题之前，先来回顾下sort的用法。

sort()方法用「原地算法」对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的「UTF-16」代码单元值序列时构建的。

如果返回值是-1，那么 a 就在 b 前面；如果返回值是1，那么 a 就在 b 后面；如果返回值是0，a 和 b 的相对位置不变(ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守)。

要比较数字而非字符串，比较函数可以简单的以 a 减 b，而不用返回-1或者1，最终的数组就会以升序排列。

sort

/**
 * @param {number[]} nums
 * @return {string}
 */
const minNumber = (nums) => {
    return nums.concat().sort((a, b) => ('' + a + b) < ('' + b + a) ? -1 : 1).join('');
};

分析：

首先，sort函数会修改原数组，因此这里拷贝一份数组再进行排序。

排序函数里的比较函数，首先将a和b转换为字符串后进行拼接，然后比较拼接后字符串的大小，将较小的排在前面。

因为最终需要返回字符串，所以这里调用join('') 函数通过空字符串将数组拼接为最终字符串并返回。

快排

除了使用内置函数来解题，我们还可以使用其他的排序方式来解题。这里使用快速排序。在排序之前先来回顾一下快排的步骤。

快排分为「哨兵划分」和「递归」。

哨兵划分就是：以数组某个元素（一般选取首元素）为 「基准数」 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

递归就是：对 「左子数组」 和 「右子数组」 分别递归执行 「哨兵划分」，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

/**
 * @param {number[]} nums
 * @return {string}
 */
const quickSort = (nums, l, r) => {
    if (l >= r) return; // 递归终止条件
    let i = l; // 初始化左指针
    let j = r; // 初始化右指针
    while(i < j) {

    // 寻找第一个小于哨兵的值
        while(i < j && ('' + nums[j] + nums[l]) >= ('' + nums[l] + nums[j])) j--;

    // 寻找第一个大于哨兵的值
        while(i < j && ('' + nums[i] + nums[l] <= ('' + nums[l] + nums[i]))) i++;

    // 交换两个值
        [nums[i], nums[j]] = [nums[j], [nums[i]]]
    }

  // 将哨兵与左指针交换，哨兵位于正确的位置
    [nums[l], nums[i]] = [nums[i], nums[l]]

  // 递归的排序左右子数组
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r)
}

const minNumber = (nums) => {
    quickSort(nums, 0, nums.length - 1); // 开始快排
    return nums.join('') // 拼接为字符串并返回
};

• 「时间复杂度 O(nlogn)」。
• 「空间复杂度 O(n)」。

分析：

首先看复杂度方面，使用快排或者内置函数的平均时间复杂度为O(nlogn)，而极端情况会退化为O(n^2) ，具体原因在后续分析排序算法时详说，此处重点分析快排的过程。字符串会占用O(n)的额外空间。

接下来具体说明快排的过程。主函数内就是调用快排函数，因为快排是原地修改数组，所以不需要返回值。由于快排是递归的进行，所以首先需要声明递归的终止条件。

快排函数的三个参数分别表示：当前需要排序的数组、子数组的左边界、子数组的右边界。当左边界大于等于右边界时，意味着子数组中只有一个元素，此时直接返回。

然后声明两个指针。默认情况下，分别指向当前递归的左边界和右边界。此时我们默认将左边界所在的元素指定为「哨兵」。在左指针小于右指针的前提下，分别寻找第一个小于哨兵的值和第一个大于哨兵的值，然后交换两个值。本轮循环结束后，再将左边界的值(哨兵)和已经右移的左指针的值进行交换。经历过此次循环并交换哨兵位置后，哨兵前面所有的值都小于哨兵，后面所有的值都大于哨兵。也就意味着哨兵的位置就是正确的，不需要再改变。

然后再递归的排序哨兵前面的左子数组和后面的右子数组。注意不包含哨兵，因为哨兵的位置是正确的，不需要再变动。

最终需要拼接为字符串并进行返回。

总结

本题考查排序。采用了内置函数和快排的思路进行题解。重点需要掌握快排的逻辑，需要注意的是，快排的效率优于冒泡排序和堆排序，但是不稳定。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59ypcj/