哈希表题目：数组中重复的数据网站首页 技术杂谈

哈希表题目：数组中重复的数据

伟大的车尔尼 2023-05-28 16:00:02

简介哈希表题目：数组中重复的数据

文章目录

题目
解法

题目

标题和出处

标题：数组中重复的数据

出处：442. 数组中重复的数据

难度

6 级

题目描述

要求

给你一个长度为 $n$ 的整数数组 $nums$ ，其中 $nums$ 的所有整数都在范围 $[1, n]$ 内，且每个整数出现一次或两次。请你找出所有出现两次的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 $O(n)$ 且仅使用常量额外空间的算法解决此问题。

示例

示例 1：

输入： $nums = [4,3,2,7,8,2,3,1]$
输出： $[2,3]$

示例 2：

输入： $nums = [1,1,2]$
输出： $[1]$

示例 3：

输入： $nums = [1]$
输出： $[]$

数据范围

$n = nums.length$
$exttt{10}^ exttt{5}$
$1 \leq nums[i] \leq n$
$nums$ 中的每个元素出现一次或两次

解法

思路和算法

这道题要求找出数组 $nums$ 中的所有出现两次的整数并返回。常规的做法是使用哈希表存储数组中的整数，遍历数组并将每个整数存入哈希表，如果遍历到一个元素时发现该元素已经在哈希表中，则该元素是出现两次的整数。对于长度为 $n$ 的数组，使用哈希表的时间复杂度是 $O (n)$ ，符合题目要求，但是空间复杂度是 $O (n)$ ，不符合题目要求的常数空间。

为了将空间复杂度降低到常数，不能额外创建哈希表，只能原地修改数组。由于数组 $nums$ 的长度是 $n$ ，下标范围是 $[0, n - 1]$ ，每个元素都在范围 $[1, n]$ 内，因此可以将数组看成哈希表，利用数组下标的信息表示每个整数是否出现两次。对于下标 $index$ ，满足 $0 \leq index < n$ ， $1 \leq index + 1 \leq n$ ， $nums [index]$ 可以用于表示整数 $index + 1$ 是否出现两次。

遍历数组 $nums$ 。对于元素 $num$ ，其对应的下标为 $index = ∣ num ∣ - 1$ ，根据 $nums [index]$ 的正负性执行如下操作：

如果 $nums [index] > 0$ ，则将 $nums [index]$ 的值更新为其相反数；
如果 $nums [index] < 0$ ，则 $∣ nums ∣ = index + 1$ 是出现两次的整数，将其添加到结果中。

上述做法的原理如下：

初始时数组 $nums$ 中的整数都是正数，表示尚未被访问；
当一个整数被访问时，如果该整数对应的下标处的元素是正数，则该整数尚未被访问，因此将该整数对应的下标处的元素改成其相反数，相反数是负数，表示被访问了一次；
当一个整数被访问时，如果该整数对应的下标处的元素是负数，则该整数已经被访问，因此该整数被第二次访问，即该整数是出现两次的整数。

需要注意的是，遍历数组 $nums$ 的过程中，遍历到的元素 $num$ 可能已经被改成负数，因此在计算下标 $index$ 时需要对 $num$ 取绝对值然后减 $1$ 。

代码

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