AcWing 13. 找出数组中重复的数字

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 13. 找出数组中重复的数字原题链接简单

作者：

yxc , 2019-01-05 02:32:08 , 所有人可见 , 阅读 26220

150

56

算法

(数组遍历) $O(n)$

首先遍历一遍数组，如果存在某个数不在0到n-1的范围内，则返回-1。

下面的算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i。

从前往后遍历数组中的所有数，假设当前遍历到的数是 $nums[i] = x$，那么：

如果x != i && nums[x] == x，则说明 $x$ 出现了多次，直接返回 $x$ 即可；
如果nums[x] != x，那我们就把 $x$ 交换到正确的位置上，即 swap(nums[x], nums[i])，交换完之后如果nums[i] != i，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以swap操作最多会进行 $n$ 次，不会发生死循环。

循环结束后，如果没有找到任何重复的数，则返回-1。

时间复杂度分析

每次swap操作都会将一个数放在正确的位置上，最后一次swap会将两个数同时放到正确位置上，一共只有 $n$ 个数和 $n$ 个位置，所以swap最多会进行 $n - 1$ 次。所以总时间复杂度是 $O(n)$。

C++ 代码

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

61 评论

上下求索 2022-03-06 08:38

class Solution {
public:
    int cnt[1010];
    int duplicateInArray(vector<int>& a) {
        memset(cnt,0,sizeof cnt);
        int n=a.size();
        for(int x:a)if(x<0||x>=n)return -1;
        for(int x:a)if(++cnt[x]>1)return x;
        return -1;
    }
};

RyuShin-wi 2023-09-24 15:47

class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
int n=nums.size();
for(auto x:nums)//对nums中逐个元素的复制引用
{
if(x<0||x>=n)
return -1;
}
for(int i=0;i<n;i)
{
for(int j=i+1;j<n;j)
{
if(nums[i]==nums[j])
return nums[i];
}
}
return -1;
}
};

人机 10天前

class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
const int n=nums.size();
if(n==0) return -1;
int arr[n]={0};
int temp=-1;
for(auto i:nums)
{
if(i>n-1||i<0) return -1;
arr[i]++;
if(arr[i]==2)
temp=i;
}
return temp;
}
};

jupyter 3个月前

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        # 判断所有数字是否满足0-n-1的条件
        n = len(nums)
        for num in nums:
            if num < 0 or num > n:
                return -1

        # 把所有数字移动到正确的位置
        for i in range(n):
            # 理想情况下 nums[i] == i
            if nums[i] != i and nums[nums[i]] == nums[i]:
                return nums[i]

            while nums[nums[i]] != nums[i]:
                # 交换当前位置的数和nums[i]位置的数
                x = nums[i]
                y = nums[nums[i]]
                nums[i] = y
                nums[x] = x


        return -1

这样写为啥错了？

yosMy 8个月前

不可以直接排序，然后再找重复的吗

你好流星 6个月前

可以，但这样就慢了

Fungi 2023-08-07 10:51

经典题目

谜_8 2023-06-09 23:41

先遍历是保证剩下的所有数都满足0~n-1，之后等于是在做排序，搞了省空间的排序？

没那么多因果 2023-01-15 10:54

我是只会循环的小菜

剑客泰菲 2022-09-18 10:50

我不李姐这错了啥？
语言:C
#include[HTML_REMOVED]
using namespace std;
int main(){
int n,sum=0,z,h,b[10001],c;
cin>>n;
int a[n];
for(int i=0;i[HTML_REMOVED]>a[i];
b[h]=a[i];
h;
z=a[i];
for(int x=0;x<=sum+1;x){
if(b[x]==z){
c=b[x];
sum;
}
}
}
if(sum==0){
cout<<”-1”;
}else{
cout<<c;
}
return 0;
}

过眼云烟_0 5个月前

要在他给的class里面写

长夜的emo 2022-07-29 15:08

呵呵

阿洛 2022-06-28 19:18

为什么没人用桶排做呢

阿白_728 2022-07-16 19:57

实测速度还慢了一点

Niriendil 2022-07-26 15:37

我用了，两题我都这么做的

zzuts 2022-10-04 20:33

桶排用了额外的空间，有时候算法要求使用O1的空间来做，这个思路挺好的。当然桶排也是一个解法

lymyc 2022-05-15 15:10

class Solution是什么
？

断然 2022-06-14 11:11

类似于leetcode的核心代码模式

lymyc 2022-10-01 16:03 回复了断然的评论

哦，谢谢

Mashiro_17 2022-03-15 15:34

从第一个nums[0]开始感觉就对不上了，nums[0]!=0,那不是直接返回nums[0]的值了嘛

帅的被人砍 2022-04-12 17:25

交换之后，如果还相等，说明他是重复的

骄阳似火 2022-03-07 15:24

class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
int i,n=nums.size();
for(auto x:nums)
if(x<0||x>=n)
return -1;
for(i=0;i<n;i)
for(int j=i+1;j<n;j)
if(nums[i]==nums[j])
return nums[i];
return -1;
}
};

冷茶热饭 2022-03-05 17:19

这个方法绝了，强

向日葵的花语 2022-01-18 11:54

奇奇怪怪的想法，诀绝子

吕德华 2022-01-16 00:11

y总，这题如果使用map，空间复杂度和时间复杂度各是多少呢，都是logN吗

五月渔郎 2021-03-15 09:31

请问要是只输出第一个重复数字该怎么改呢？[6,3,2,0,2,5,0]比如这个输出就是0 但是实际应该是2

Huracán 2022-06-07 22:55

我是考虑先使用sort对nums进行排序，只要找到两个相邻的数值相同就返回当前数值
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == nums[i + 1])
return nums[i];
}