[LeetCode] 442. Find All Duplicates in an Array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

Constraints:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.

数组中重复的数据。

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意是给一个数组，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。要求不使用额外空间。

思路是类似抽屉原理/桶排序。遍历input数组，把当前数字N当做下标，找到对应坐标上的另一个数字，如果这个数字大于0就把他改成负数。当再次遇到N的时候，会发现对应坐标上的数字是负数，就知道N是重复的，把他加入结果集。跑例子说明吧，

input, [4, 3, 2, 7, 8, 2, 3, 1]

一开始遍历到4，他对应的index应该是4 - 1 = 3，则去改动nums[3]位置上的数字7，把他改成负数，[4, 3, 2, -7, 8, 2, 3, 1]

再来遍历到3，对应的index是3 - 1 = 2，去改动nums[2]位置上的数字，把他改成负数，[4, 3, -2, -7, 8, 2, 3, 1]

再来遍历到-2，因为当前数字已经是负数了，所以找index的时候需要取绝对值，所以他对应的index是2 - 1 = 1，去改动nums[1]位置上的数字，把他改成负数，[4, -3, -2, -7, 8, 2, 3, 1]

再来遍历到-7，因为当前数字已经是负数了，所以找index的时候需要取绝对值，所以他对应的index是7 - 1 = 6，去改动nums[6]位置上的数字，把他改成负数，[4, -3, -2, -7, 8, 2, -3, 1]

再来遍历到8，对应的index是8 - 1 = 7，去改动nums[7]位置上的数字1，把他改成负数，[4, -3, -2, -7, 8, 2, -3, -1]

再来遍历到2，对应的index是2 - 1 = 1，发现index = 1的位置上已经是一个负数了，所以跟index有关的的数字2是重复的数字，加入结果集

再来遍历到-3，因为当前数字已经是负数了，所以找index的时候需要取绝对值，所以他对应的index是3 - 1 = 2，发现index = 2的位置上已经是一个负数了，所以跟index有关的的数字3是重复的数字，加入结果集

再来遍历到1，对应的index是1 - 1 = 0，去改动nums[0]位置上的数字，把他改成负数，[-4, -3, -2, -7, 8, 2, -3, -1]。最后结果集里是[2, 3]

时间O(n)

空间O(1) - required

Java实现

 1 class Solution {
 2     public List<Integer> findDuplicates(int[] nums) {
 3         List<Integer> res = new ArrayList<>();
 4         if (nums == null || nums.length == 0) {
 5             return res;
 6         }
 7         for (int i = 0; i < nums.length; i++) {
 8             int index = Math.abs(nums[i]) - 1;
 9             if (nums[index] < 0) {
10                 res.add(Math.abs(index + 1));
11             }
12             nums[index] = -nums[index];
13         }
14         return res;
15     }
16 }