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?

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

题目大意:
给定一个整数数组,1 <= a[i] <= n (n = 数组长度),某些元素出现两次,某些出现一次。寻找数组中所有出现两次的元素。你可以不使用额外空间并且在O(n)运行时间内完成题目吗?

思路:

解法一(自己的想法):首先对数组进行排列,例如[4,3,3,2,1] 排列后变为[1,2,3,3,4],遍历nums,当nums[i] - nums[i + 1] == 0时,也就是当前数字等于下一个数字,再将当前数字存入数组中。

代码:

1
2
3
4
5
6
7
8
9
10
11
public static List<Integer> findDuplicates1(int[] nums) {
List<Integer> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] - nums[ i+1 ] == 0){
res.add(nums[i]);
i++;
}
}
return res;
}

解法二:正负号标记法(一趟遍历)

遍历nums,记当前数字为n(取绝对值),将数字n视为下标(因为a[i]∈[1, n])

当n首次出现时,nums[n - 1]-1

当n再次出现时,则nums[n - 1]一定<0,将n加入答案

参考:https://discuss.leetcode.com/topic/64735/java-simple-solution
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.

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;
}
}
0%