interviewalgo
, , ,
Source
Edit
History

442. 数组中重复的数据

Introduction

Question: 442. 数组中重复的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<p>给定一个整数数组 a，其中1 &le; a[i] &le; <em>n</em> （<em>n</em>为数组长度）, 其中有些元素出现<strong>两次</strong>而其他元素出现<strong>一次</strong>。</p>

<p>找到所有出现<strong>两次</strong>的元素。</p>

<p>你可以不用到任何额外空间并在O(<em>n</em>)时间复杂度内解决这个问题吗？</p>

<p><strong>示例：</strong></p>

<pre>
<strong>输入:</strong>
[4,3,2,7,8,2,3,1]

<strong>输出:</strong>
[2,3]
</pre>

解法一

Analysis

与 LC448-find-all-numbers-disappeared-in-an-array几乎一样，只要修改一下最后产生输出的判断即可。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> findDuplicates(vector<int>& nums) {
    int n = nums.size();
    for(int i = 0;i < n; i++) {
        int index = (nums[i]-1) % n;
        nums[index] += n;
    }
    vector<int> res;
    for(int i = 0;i < n; i++) {
        if (nums[i] > 2*n) {
            res.push_back(i+1);
        }
    }
    return res;
}