[数据结构与算法]442. 数组中重复的数据

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 中的每个元素出现 一次 或 两次

2. 题目解答

思路一

观察本题的条件可以知道，数组的整数范围在[1, n]，所以我们可以利用集合来计算每个元素的出现次数，具体步骤是：

1. 初始化集合为0
2. 统计数组个元素出现次数
3. 将出现次数为 2的设置为对应的值，即是其索引
4. 删除多余元素

代码一

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>(n+1);
        //初始化集合为0
        for (int i = 0; i <= n; i++) {
            res.add(0);
        }
        //统计数组个元素出现次数
        for (int i = 0; i < n; i++) {
            res.set(nums[i],res.get(nums[i])+1);
        }
        //将出现次数为 2的设置为对应的值，即是其索引
        for (int i = 1; i <= n; i++) {
            if(res.get(i) == 2) res.set(i,i);
            else res.set(i,0);
        }
        //删除多余元素
        for (int i = 0; i < res.size(); i++) {
            if(res.get(i) == 0){
                res.remove(i--);
            }
        }
        return res;
    }
}

注意：上面的是一种代码思路，就是用来解决数组内的元素大小不超过数组长度，可以利用数组索引和数组元素的对应关系来解决一系列问题

思路二

考虑到题目已告诉数组元素只出现一次或两次，所以可以利用取反，具体步骤如下：

1. 根据数组元素-1 = 数组索引
2. 遍历数组
   1. 数组索引中大于0的数组元素取反
   2. 数组索引小于0的数组元素加入结果集中，原因是该元素原本是正数，现在是负数，证明前面已经出现过一次

代码二

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

3. 知识点

题目总结

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内

题目出现上述条件应该想到数组元素和数组索引的对应关系

list数组删除元素的代码

 //删除元素
List<Integer> list = new ArrayList<>(n+1);
for (int i = 0; i < list.size(); i++) {
        res.remove(i--);
}

4. 参考

https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/solution/by-fuxuemingzhu-dko5/

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖