LeetCode442 Find All Duplicates in an Array

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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?

样例

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

思路

找出所有在数组中出现两次的数。

类似LeetCode448 Find All Numbers Disappeared in an Array这题中的技巧,对原数组做标记(取个负)表示该数曾出现过,若下次遇到已经为负则说明重复出现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size(), id;
vector<int> ans;
for (int i = 0; i < n; ++i) {
id = abs(nums[i]) - 1;
if (nums[id] < 0) ans.push_back(id + 1);
nums[id] *= -1;
}
return ans;
}
};
分享到 评论