1.题目介绍

题目地址(442. 数组中重复的数据 - 力扣（LeetCode）)

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

题目描述

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

2.题解

2.1 哈希表

思路

哈希表记录出现次数,但是这种方法是错误的,并不满足使用常量级空间存储哈希表的要求!!!

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_map<int, int> mp;
        int n = nums.size();
        for(int num: nums){
            if(mp.count(num)){
                mp[num]++;
            }else{
                mp.emplace(num, 1);
            }
        }

        vector<int> ans;
        for(int i = 1; i <= n; i++){
            if(mp[i] == 2){
                ans.push_back(i);
            }
        }
        return ans;
    }
};

复杂度分析

令 n 为数组长度。

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

2.2 交换位置

思路

我们知道应该将num[i] 这个值放到对应 nums[nums[i] - 1]的位置上, 所以我们考虑遍历数组, 进行 swap(num[i], nums[nums[i] - 1]), 这样就行了吗?
不行, 换出的值位置是对了, 换进来的却是不对的, 但是我们是按照从前向后的顺序执行,换进前面的数如果不对,后面就有可能一直不对下去,导致错误
[4,3,2,7,8,2,3,1]
0 [7,3,2,4,8,2,3,1]
1 [7,2,3,4,8,2,3,1]
2 [7,2,3,4,8,2,3,1]
3 [7,2,3,4,8,2,3,1]
4 [7,2,3,4,1,2,3,8]
5 [7,2,3,4,1,2,3,8]
6 [7,2,3,4,1,2,3,8]
7 [7,2,3,4,1,2,3,8]

我们思考后, 猜想是否应该保证遍历时每次的首项正确即可? 即最后下标 == 值 - 1 ;(i == nums[i] - 1;)
像是加上 while (i != nums[i] - 1) 可以吗? 保证位置0对应1,位置1对应2.... 错误的, 这样判断如果对应位置的数不存在,比如像如果数组中不存在3,就会不断交换导致死循环!!!!

正确思路应该是: while (nums[i] != nums[nums[i] - 1]) , 想法和上面还是一样的下标 == 值 - 1
while循环的停止条件 1. 重复元素-两个位置[i 和 nums[i] - 1]](像是下面例子中的两个3) 2.元素处于正确位置
这样就不是保证每个位置i对应的值都正确, 而是保证数组中所有存在的数作为位置下标nums[i], 值为 nums[nums[i] - 1]
执行的顺序不是按0-n, 而是按遍历数组的元素顺序来(每次确保数组的每一个元素位置正确), 最后停止时当前位置元素必定为重复元素/位于正确位置的数组元素, 前面不可能还有没有正确排位置的数组元素, 故继续向后遍历
[4,3,2,7,8,2,3,1]
0.1 [7,3,2,4,8,2,3,1]
0.2 [3,3,2,4,8,2,7,1]
0.3 [2,3,3,4,8,2,7,1]
0.4 [3,2,3,4,8,2,7,1]
1.1 [3,2,3,4,8,2,7,1]
2.1 [3,2,3,4,8,2,7,1]
3.1 [3,2,3,4,8,2,7,1]
4.1 [3,2,3,4,1,2,7,8]
4.2 [1,2,3,4,3,2,7,8]
5.1 [1,2,3,4,3,2,7,8]
6.1 [1,2,3,4,3,2,7,8]
7.1 [1,2,3,4,3,2,7,8]
经检查[5,6]不在数组中!

代码

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans; 
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]); // 这里切不可只交换一次, 我们考虑一种极端情况,如果第一个数和第i个数交换后,第一个数到达正确位置,而第i个数到达错误位置
        }

        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
};

2.3 索引-值

思路

同力扣-448. 找到所有数组中消失的数字
那里是出现零次和一次的数,这里是出现一次和两次的数,原理是一样的

代码

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans; 
        int n = nums.size();
        for(int i = 0; i < n; i++){
            int x = (nums[i] - 1) % n;
            nums[x] += n;
        }

        for(int i = 0; i < n; i++){
            if(nums[i] > 2 * n){
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};

2.3 正负号标记

思路

思路同2.2, 我们需要一个能实时还原为下标的标记,然后就可以使用该标记判断哪些元素时重复出现了
这里使用正负号, 标记的时候使其变负即可; 而还原的时候简单的使用abs即可还原!

代码

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans; 
        int n = nums.size();
        for(int i = 0; i < n; i++){
            int x = abs(nums[i]) - 1;  
            if(nums[x] > 0){
                nums[x] = -nums[x];
            } else{
                ans.push_back(x + 1);
            }         
        }
        return ans;
    }
};

标签：nums,int,442,位置,力扣,vector,数组,ans
From： https://www.cnblogs.com/trmbh12/p/18158142

力扣-442. 数组中重复的数据