数组中重复的数据

说在前面

🎈每天进行一道算法题目练习，今天的题目是“数组中重复的数据”。

问题描述

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

思路分析

阅读完题目后我们知道，题目是要我们找出数组中所有出现了两次的元素。\
这样看来题目好像十分简单，我们直接来两个for循环就可以暴力求出题目的答案了，但是真的这么简单吗？让我们再来好好看一遍题目，我们会找到这么一个要求限制你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题,也就是说我们只能进行一次循环来求解，这样一来是不是就有一点挑战性了？那么接下来就让我们一起来思考该如何完成这一道题目。
我们可以将数字和下标对应起来，如数字4应该放在下标3的位置，我们只需要将对应下标的位置上都放入对应的数字，最后我们只需要在判断数字是否在其对应下标和其他位置同时出现即可，关键代码如下：

• 1、数组元素位置交换

const swap = function(nums,ind1,ind2){
    [nums[ind1],nums[ind2]] = [nums[ind2],nums[ind1]];
}

• 2、将数组元素交换到指定下标

for(let i = 0; i < nums.length; i++){
    while(nums[nums[i] - 1] != nums[i]) swap(nums,i,nums[i] - 1);
}

• 3、找出重复的数字

for(let i = 0; i < nums.length; i++){
    if(nums[i] == i + 1) continue;
    if(nums[nums[i] - 1] == nums[i]) res.push(nums[i]);
}

AC代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var findDuplicates = function(nums) {
     const swap = function(nums,ind1,ind2){
         [nums[ind1],nums[ind2]] = [nums[ind2],nums[ind1]];
     }
     const res = [];
     for(let i = 0; i < nums.length; i++){
         while(nums[nums[i] - 1] != nums[i]) swap(nums,i,nums[i] - 1);
     }
     for(let i = 0; i < nums.length; i++){
        if(nums[i] == i + 1) continue;
        if(nums[nums[i] - 1] == nums[i]) res.push(nums[i]);
     }
     return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。