[leetcode] 442. Find All Duplicates in an Array
程序员文章站
2024-02-17 11:41:28
...
Description
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
分析
题目的意思是:找出数组中出现两次的值。
- 这类问题的一个重要条件就是1 ≤ a[i] ≤ n (n = size of array),不然很难在O(1)空间和O(n)时间内完成。首先来看一种正负替换的方法,这类问题的核心是就是找nums[i]和nums[nums[i] - 1]的关系,我们的做法是,对于每个nums[i],我们将其对应的nums[nums[i] - 1]取相反数,如果其已经是负数了,说明之前存在过,我们将其加入结果res中即可.
- 如果读者不明白其过程,把题目中的那个例子模拟一下就好了,
代码
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
for(int i=0;i<nums.size();i++){
int idx=abs(nums[i])-1;
if(nums[idx]<0) res.push_back(idx+1);
nums[idx]=-nums[idx];
}
return res;
}
};
参考文献
推荐阅读
-
[leetcode] 442. Find All Duplicates in an Array
-
【LeetCode】442. Find All Duplicates in an Array(找出数组中的重复项)
-
[leetcode] 442. Find All Duplicates in an Array
-
leetcode 442. Find All Duplicates in an Array
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
LeetCode448 — Find All Numbers Disappeared in an Array
-
LeetCode442 — Find All Duplicates in an Array
-
leetcode 448. Find All Numbers Disappeared in an Array
-
LeetCode-448. Find All Numbers Disappeared in an Array
-
Leetcode 448. Find All Numbers Disappeared in an Array (python+cpp)