442. Find All Duplicates in an Array

发表于 | 分类于

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：

这题比较关键的是题目的条件，数字在1和n之间。那么用置换的办法可以达到复杂度的要求。对于每一个数字，如果没有重复，排序之后他应该在i+1上。
那么我们可以把每一个数字归位。要注意，如果i和j置换了，i不应该往前进而是应该停留原地（i–那行很重要）
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // Use the condition that num in nums are between 1 and n
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp -1];
                nums[temp - 1] = temp;
                i--;        // very important
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1) {
                res.add(nums[i]);
            }
        }
        return res;
    }
}