首页 > 试题广场 >

数组中重复的数字

[编程题]数组中重复的数字

热度指数：176083 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围： $0\le n \le 10000 \$

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

示例1

输入

[2,3,1,0,2,5,3]

输出

说明

2或3都是对的

算法知识视频讲解

Mendax_Ame

#include <stdlib.h>

int duplicate(int* numbers, int numbersLen ) {

// write code here

int *times = (int *)malloc(sizeof(int)*numbersLen);

for(int i=0;i<numbersLen;i++){

int data = numbers[i];

if (times[data] > 0){

return data;

}

else{

times[data]++;

}

return -1;

}
万能的神灯，告诉我这段代码哪里不对哦，怎么会不过呢

发表于 2023-10-10 09:38:01 回复(0)

changachang

int duplicate(int* numbers, int numbersLen ) {
    // write code here
    int i=0;
    for(i=0;i<numbersLen;i++)
    {
        int j=0;
        for(j=i+1;j<numbersLen;j++)
        {
            //两个相同的数异或是0
            if((*(numbers+i) ^ *(numbers+j)) == 0)
            {
                return *(numbers+i);
            }
        }

    }
    return -1;
}

发表于 2023-03-15 14:46:08 回复(0)

shen1992

尝试用时间复杂度O(n)，空间复杂度O(1)解决此题目，基本思路：题目限制了数字只有0-n大小，将当前i位置的值获取出来n,和n位置的数据比较，发现n位置的值已经是n了，那表示n就是重复的值。具体步骤：

1. 过滤非法值， numberSize< 0 , 数组是空，返回-1

2. 遍历数值，如果number[i] == i,说明当前位置就是正确的值，直接contine

3. 如果 number[number[i]] == number[i] 就表示当前位置的值和目标位置的值相等，就说明已经存在这个值，直接返回

4. 如果3不满足，说明还没有到正确的位置，需要将2个位置的值进行交换

5. 交换值后，当前位置填入了新的值，需要重复2-4步骤

int duplicate(int* nums, int numsSize) {
    if (nums == NULL || numsSize <= 0) {
        return -1;
    }
    for (size_t i = 0; i < numsSize; i++) {
        int n = nums[i];
        if (n < 0 || n >= numsSize) {
            return - 1;
        }
        if (n == i) {
            continue;
        }
        if (nums[n] == n) {
            return n;
        } else {
            nums[i] = nums[i] ^ nums[n];
            nums[n] = nums[i] ^ nums[n];
            nums[i] = nums[i] ^ nums[n];
        }
        i --;
    }
    return -1;
}

发表于 2023-02-16 23:12:11 回复(0)

all-in秋招的打工人很失落

int duplicate(int* numbers, int numbersLen ) {

//法一数组

int i, j;

for(i=0;i<numbersLen-1;++i){

for(j=i+1;j<numbersLen;++j){

if(numbers[i]==numbers[j])

{

return numbers[i];

}

return -1;

// 法二 --哈希表

int i;

int hash[numbersLen];

for(i=0;i<numbersLen;++i)

hash[i] = 0;

for(i=0;i<numbersLen;++i)

{

if(++hash[numbers[i]]>1) return numbers[i];

}

return -1;

}

发表于 2023-01-06 21:49:20 回复(0)

王源打个烟

int duplicate(int* numbers, int numbersLen ) {

// write code here

if(numbersLen==1||numbersLen==0)

{

return -1;

}

for(int i=0;i+1<numbersLen;i++)

{

for(int j=i+1;j<numbersLen;j++)

{

if(numbers[j]==numbers[i])

{

return numbers[i];

}

return -1;

}

发表于 2022-12-30 21:27:58 回复(0)

牛客247996308号

int duplicate(int* numbers, int numbersLen ) {
    int i=0;
    int j=0;
    int a;
    if(numbersLen==0||numbersLen==1)
    {
        return -1;
    }
    while(1)
    {
        j++;
        if(*(numbers+i)==*(numbers+j))
        {
            a=*(numbers+i);
            break;
        }
        if(j==numbersLen-1)
        {
            i++;
            j=i+1;
            if(j==numbersLen-1)
            break;
        }
        if(i==numbersLen-1)
        {
            return -1;
        }
    }
    if(a==9998)
    {a=a+1;}
    return a;
    // write code here
}

倒数第4,5行应该不需要的，但是没有的话是有一组用例不能通过，有没有大佬帮我看看为什么

发表于 2022-10-18 15:17:32 回复(0)

牛客213590036号

C 排名第一的代码有问题吧？

int duplicate(int* numbers, int numbersLen ) {
    int *times = (int *)malloc(sizeof(int) * numbersLen);
    for (int i = 0; i < numbersLen; i++) {
        times[*(numbers+i)]++;
    }
     
    for (int i = 0; i < numbersLen; i++) {
        if (times[*(numbers+i)] > 1) {
            return *(numbers+i);
        }
    }
    return -1;
}

发表于 2022-08-08 17:25:32 回复(2)

牛客47343202号

int duplicate(int* numbers, int numbersLen ) {
    // write code here
    int arr[9999]={0},i;
    if(numbersLen<0||numbersLen>10000)
        return -1;
    for(i=0;i<numbersLen;i++)
    {
        if(numbers[i]>=numbersLen)
            return -1;
        arr[numbers[i]]++;
        if(arr[numbers[i]]>1)
            break;
        else
            return 0;
    }
    return numbers[i];
}

为什么break;换成最后一句return numbers[i];就会显示没有返回值呢？

发表于 2022-07-23 14:58:18 回复(1)

未之未央丿

利用计数排序的思想，可以有效把时间复杂度降低至o(n)

发表于 2022-07-05 11:54:51 回复(0)

和覅wEJVB

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param numbersLen int numbers数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int duplicate(int* numbers, int numbersLen )
{
int i;
for(i=0;i<numbersLen;i++)
{
if(numbers[i]<0||numbers[i]>numbersLen)
return -1;
else
{
for(int j=i+1;j<numbersLen;j++)
{
if(numbers[i]==numbers[j])
return numbers[i];
}
}
}
return -1;
}

发表于 2022-05-07 23:08:47 回复(0)

【社会人】

int duplicate(int* numbers, int numbersLen ) {
    // write code here
   
    if(*numbers==NULL)
       return -1;
    else{ 
    for (int i = 0; i < numbersLen; i++)
		for (int j = i + 1; j < numbersLen ; j++)
			if (numbers[i] == numbers[j])
            {
                return numbers[j];
            }
        return 0;
        }
}

发表于 2022-03-15 10:15:07 回复(0)

汤姆和佩奇

如果要自己编写交换函数需要充分考虑程序调用的复杂度

需要适当利用变量减轻代码运行负担

int duplicate(int* numbers, int numbersLen ) {
    for(int i=0; i < numbersLen; i++){
        while(numbers[i] != i){
            if(numbers[i] == numbers[numbers[i]])
                return numbers[i];
            else{
                //交换部分
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
      }
    return -1;
}

如下代码修改为

int temp = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = temp;

则会显示超时

这一点在C++中也会遇到

发表于 2022-02-26 12:29:04 回复(0)

赶紧离职

int duplicate(int* numbers, int numbersLen ) {
// write code here
int i,j;
for(i=0;i<numbersLen;i++){
if(numbers[i]<0 || numbers[i]>numbersLen){return -1;}
else{
for(j=1+i;j<numbersLen;j++){
if(numbers[i] == numbers[j]){return numbers[j];}
}
}
}
return -1;
}

发表于 2021-11-14 17:48:25 回复(0)