LeetCode-442 数组中重复的数据

简介: LeetCode-442 数组中重复的数据

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/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 <= 105

1 <= nums[i] <= n

nums 中的每个元素出现 一次 或 两次

解题思路

如果没有空间复杂度的需求,那么计数统计是很好的办法,但是题目要求空间复杂度为O(1),那么不使用额外的空间去完成这道题,就需要在原数组中做文章了。由于数组的数据范围是1-n,如果不重复的话,那么每一个数字k将可以放入对应的k-1的位置,如果k-1位置上的不是k,那么可以判断这个数字重复。所以第一步,将数字k尽可能的放入对应的k-1位置上,第二步遍历数组寻找k-1位置上不是k的数字,加入结果。

代码展示

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> viRet;
        for(int i = 0; i < nums.size(); i++)
        {
            while(nums[nums[i] - 1] != nums[i])
                swap(nums[nums[i] - 1], nums[i]);
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] - 1 != i)
                viRet.push_back(nums[i]);
        }
        return viRet;
    }
};

运行结果

 

相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
38 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
3月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
57 0