LeetCode442-数组中重复的数据

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-all-duplicates-in-an-array/

中文链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

题目详述

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

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

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

示例：

1
2
3
4
5
输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

题目详解

因为数组中元素 num ∈ [1, n]（n为数组长度），故 num - 1 ∈ [0, n - 1]。

  • 可以创建一个访问标志数组 vis，元素初始化为 false。
  • 遍历给定数组，在数组 vis 中对应位置设置 true。
  • 在遍历过程中，若元素在访问标志数组对应的值为 true，说明当前元素在之前出现过，将当前元素加入到结果集中。
1
2
3
4
5
6
7
8
9
10
11
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> list = new LinkedList<>();
    boolean[] vis = new boolean[nums.length];
    for (int num : nums) {
        if (vis[num - 1]) {
            list.add(num);
        }
        vis[num - 1] = true;
    }
    return list;
}

本题可以做到不用到任何额外空间并在O(n)时间复杂度内解决这个问题，这就要在给定数组上想办法。

因为数组中元素 num ∈ [1, n]（n为数组长度），故 num - 1 ∈ [0, n - 1]。

  • 当 num 首次出现时，nums[num - 1] 乘以 -1 变为它的相反数。
  • 当 num 再次出现时，若 nums[num - 1] < 0，说明当前元素在之前出现过，将 num 加入到结果集中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00442 {

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new LinkedList<>();
        for (int num : nums) {
            num = Math.abs(num);
            if (nums[num - 1] > 0) {
                nums[num - 1] *= -1;
            } else {
                list.add(num);
            }
        }
        return list;
    }
}