Loading...
墨滴

尤慕

2021/03/25  阅读:48  主题:极简黑

LeetCode 442:找到数组中的重复项

LeetCode 442:找到数组中的重复项

文章来自我的公众号,欢迎关注: LeetCode 442:找到数组中的重复项

问题:

给定一个整数由组成的数组,其中 1 ≤ a[i] ≤ n (n 是数组长度),数组中有些元素会出现两次,而有些只出些一次。

找到这个数组中出现过两次的元素。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

解析:

一个简单的解题思路是,将数组元素放在频率字典中(map),最后取出字典中频率大于1的元素即可。

TypeScript 代码:

function findDuplicates(nums: number[]): number[] {
    return nums.filter(function (this: Set<number>, v: number{
        if (this.has(v)) {
            return true;
        }
        this.add(v);
    }, new Set());
}

这里我们使用了 Set :凡是之前加过的元素都是重复的。

另外一个解答思路就比较讨巧了。

考虑到数组元素满足条件 1 ≤ a[i] ≤ n,那么 a[a[i]-1] 一定也是数组中的元素,因为 a[i]-1 下是数组所有下标的集合。

试想一下,如果我们在遍历过程中将 a[i]-1 对应的元素取反,后续遍历中如果存在 a[j] 等于 a[i],那么 a[j]-1 对应的元素一定是负数,此时 a[j] 就是那个出现了2次的元素。需要注意的是,遍历过程中后面的元素可能在之前被取反过,所以在应用 a[i]-1 时,要用 a[i] 的绝对值,即 Math.abs(a[i])-1

以数组 [2,1,1] 做推导示例:

当遍历到最后一个元素 1 时,发现之前有元素将 0 (即 1-1 ) 这个位置的元素变为负数了,所以 1 是重复的元素。

TypeScript 代码如下:

function findDuplicates(nums: number[]): number[] {
    return nums.reduce((p, v, i, a) => {
        // 当前元素的绝对值,防止之前被取反过
        const val = Math.abs(v);
        // 需要被取反的元素
        const target = val - 1;

        // 如果该元素已经被取反过,说明 val 是重复的元素,加入到返回值中
        // 否则进行取反操作
        a[target] < 0 ? p.push(val) : (a[target] = -a[target]);
        return p;
    }, [] as number[]);
}

上面两段代码中分别用到了 Array 对象 的 filterreduce 方法,在解决实际问题时,它们相当有用。

- END -

尤慕

2021/03/25  阅读:48  主题:极简黑

作者介绍

尤慕