剑指offer - 数组中重复的数字

不会吧? 不会吧? 不会还有人认为前端工程师不用学习算法吧? 我们看看第一个题目:

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

我看到后, 用了自以为很优雅的方式实现了...

function findRepeatNumber(nums: number[]): number {
    const counter: number[] = new Array(nums.length);
    counter.fill(0);
    return nums.find(n => counter[n]++) as number;
};

仔细研究一下, 发现还有很多可优化的空间. 比如 Array 换成 Int32Array 来提升性能:

function findRepeatNumber(nums: number[]): number {
    const counter = new Int32Array(nums.length);
    return nums.find(n => counter[n]++) as number;
};

但就算用c++实现, 变成webassembly, 那程序的本质是没变的. 这样就走进了死胡同(貌似也感觉到有什么不妥).

早期在算力和空间都不充足的情况下, 程序员可是必须要在时间和空间上做权衡的. 现代设备算力的提升和空间的成本降低, 已经让我们麻木, 对提高代码执行效率的改进都嗤之以鼻.

硬是要解释之前的代码的话, 这是空间换时间的方法的一种, 只需要扫描一次列表就可以知道结果, 时间复杂度是O(n), 空间复杂度是O(n). 那这样不是也挺好的吗? 难道改成时间换空间? 通过类似排序数组的操作, 时间复杂度最快是O(nlogn). 而这样实现的方法并不会让我们有很强的成就感, 那到底要怎么样呢?

上述思路可以用如下代码实现:

function findRepeatNumber(nums: number[]): number {
    for (let i = 0; i < nums.length; ++i) {
        while (nums[i] !== i) {
            if (nums[i] === nums[nums[i]]) {
                return nums[i]
            }
            const tmp = nums[i]
            nums[i] = nums[tmp]
            nums[tmp] = tmp
        }
    }
    return -1
};

这是一个时间复杂度是O(nlogn)的解法, 空间复杂度为O(1)的算法. 到了这一步, 足以让人领会到算法的魅力, 估计也是这道题排在书中前面的原因吧.

pikou1995 / pikou1995.github.io

剑指offer - 数组中重复的数字 #5

示例 1：