LeetCode_原地哈希_中等_442.数组中重复的数据

谁践踏了优雅 2023-10-06 23:37 12阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个长度为 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  
1 <= n <= 105  
1 <= nums\[i\] <= n  
nums 中的每个元素出现一次或两次

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-all-duplicates-in-an-array

## 2.思路 ##

（1）哈希表  
**如果不考虑空间复杂度**，我们可以使用哈希表来存储数组 nums 中每个元素以及其对应出现的次数，然后再取出哈希表中出现次数为 2 的元素并将其保存到 res 中，最后再返回 res 即可。

（2）原地哈希（正负号标记）  
思路参考[本题官方题解][Link 1]。

由于数组 nums 的所有整数都在范围 \[1, n\] 内，而 nums 的长度正好为 n，所以我们可以构建 x - 1 ∈ \[0, n - 1\] 到 nums\[0…n - 1\] 之间的映射，通过标记 nums\[x - 1\] 的正负值来判断 x 出现的次数，具体步骤如下：

遍历数组 nums 中的每一个元素 x = Math.abs(nums\[i\])（此处要加绝对值是因为后面会改变数组 nums 中元素的符号），那么如果判断 x 是出现了 1 次还是 2 次呢？很简单，由于 x ∈ \[1, n\]，那么 x - 1 ∈ \[0, n - 1\] 正好在 nums 的下标范围内，所以我们可以进行如下判断：

*  如果 nums\[x - 1\] > 0，那么我们认为 x 此时只出现了一次，为了方便判断 x 下次是否出现，我们将 nums\[x - 1\] 取负号；
 *  如果 nums\[x - 1\] < 0，那么这说明 nums\[x - 1\] 在之前已经被取过一次负号，进而可以推出 x 之前已经出现过一次，所以此时的 x 已经是第 2 次出现，故直接将其加入到 res 中；

遍历结束后，直接返回 res 即可。**该方法的时间复杂度为 O(n)，空间复杂度为 O(1)（返回值的空间复杂度不计算在内）**

小结：一般像这种要求使用常量额外空间且题目中与次数、次数有关的题目，我们可以首先联想到使用**原地哈希**，使用原地哈希的一个关键在于使用原数组（或者其它容器）作为哈希表，将原数组中的元素作为键（即看作数组中的下标），建立起适合题目条件的对应关系。

## 3.代码实现（Java） ##

//思路1————哈希表
    class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            List<Integer> res = new ArrayList<>();
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int num : nums) {
        
                hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
            }
            for (int num : hashMap.keySet()) {
        
                if (hashMap.get(num) == 2) {
        
                    res.add(num);
                }
            }
            return res;
        }
    }

//思路2————原地哈希（正负号标记）
    class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
        
                int x = Math.abs(nums[i]);
                if (nums[x - 1] > 0) {
        
                    nums[x - 1] = -nums[x - 1];
                } else {
        
                    res.add(x);
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/find-all-duplicates-in-an-array/solution/shu-zu-zhong-zhong-fu-de-shu-ju-by-leetc-782l/