题目描述

给定一个长度为 n的整数数组 nums，数组中所有的数字都在 0∼n−1的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1
的范围内，或数组中不包含重复数字，则返回 -1；

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法及其源码（c语言）

int duplicateInArray(int *nums, int numsSize) ##函数名称
{

int i,j;    ##循环变量
int count;      ##重复检测计数器


for(i=0;i<numsSize;i++) 
##检测是否存在越界数据，越界返回-1，未越界情况全体加1（后面解释+1的作用）

{
    if(nums[i]<0||nums[i]>numsSize-1)   ##越界判断
    {
        return -1;
    }
    else
    {
        nums[i]++;      ##全体加1
    }
}


for(i=0;i<numsSize;i++)     ##第一个循环表示检测轮数
{
    for(j=0;j<numsSize;j++)     ##第二个循环表示遍历数组元素
    {
        nums[j]--;      ##这里体现了加1的作用，若前面不进行加1操作，这里出现重复的初始数0会被忽视
        ##每经过一轮，数组的数据都会被减一

        if(nums[j]==0)
        {
            count++;    ##对数组中数据进行检测，若出现0的情况，将重复检测计数器+1
        }
    }


    if(count>1)     ##若重复检测计数器大于1，说明遭遇了重复数据的情况
    {
        return i;       ##这里返回当前轮数的原因是因为大小为n的数据会在第n轮被上述操作减到0，返回当前轮数就是返回重复数据最初始的值
    }

    count=0;    ##每轮结束后，重置重复检测计数器以便下一轮使用

}

return -1;      ##若所有轮次结束后都没有发现重复数据，依照题意返回-1

}