LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数

题目描述

442 Find All Duplicates in an Array
https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/
https://leetcode.com/problems/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]

---

解题过程

相似题目
LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数
LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数
LeetCode.041.First Missing Positive 数组中缺失的第一个正数

一看到题干中的 1 ≤ a[i] ≤ n ，就知道肯定是用数组下标技巧做。
原地哈希，在输入数组本身以某种方式标记已访问过的数字，对于数据中的每个值 a[i] ，将值 a[a[i]] 取反来表示这个值出现过 。
但是下标a[i]上原有的值不能被覆盖，那怎么办呢？在这里我着实思考了一会儿，然后发现可以将下标a[i]上的值减去数组a的长度来表示已被标记，非常巧妙：

时间复杂度 O(n)，空间复杂度 O(1)

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<nums.length; i++){
            //有的被标记过的值已经是负的，需要对其进行加nums.length还原
            int realindex = nums[i]>=1 ? nums[i] : nums[i]+nums.length;
            if(nums[realindex-1] >= 1){//下标位nums[i]没有被标记过
                //把下标位nums[i]的值减nums.length，以此来表示此下标位的值存在
                nums[realindex-1] -= nums.length;
            }else{//已被标记过的值肯定<=0
                list.add(realindex);
            }
        }
        return list;
    }
}

并且满足O(n)时间复杂度且无额外空间开销的要求，速度很快，打败了77%的代码。

提交之后看Discuss，发现一个更简洁的代码，思路相同，但人家是将 下标a[i] 处的值设为负的来标记，更巧妙：

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }
}

这位大神解释自己的思路时描述的也非常好：

I was thinking we need a way to “hash” the same number together without using extra space. I am inspired by the range of the input value (1 - N), which seems fit the index of the input array (0 - N-1).
If I hash num[i] to index num[i]-1, then I need to store it at index num[i]-1 smartly. I shouldn’t make irrecoverable change to the element at that position, because I may need the element in the future. Again using the given range of input is (1 - N), if flip it to the opposite I can still recover it using Math.abs

这类方法的缺点是只能找到重复的数，但无法知道重复了几次。

---

GitHub代码

algorithms/leetcode/leetcode/_442_FindAllDuplicatesInArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_442_FindAllDuplicatesInArray.java

---