尤慕
V1
2021/03/25阅读:95主题:极简黑
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 对象 的 filter 和 reduce 方法,在解决实际问题时,它们相当有用。
- END -作者介绍
尤慕
V1