每日一练（剑指offer)数组中重复的数字

描述

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

数据范围：

进阶：时间复杂度

，空间复杂度

示例1

输入：

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

复制

返回值：​

2

复制

说明：

2或3都是对的

分析

下标法：通过不停交换元素使的元素的值和它所对应的下标相等，因为元素是有重复

的，这样的话肯定会有多个元素对应一个下标，这个时候可以判断它是否重复了

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int duplicate(int* numbers, int numbersLen)
{
for (int i = 0; i < numbersLen; i++)
  {//用while交换后，该位置的元素耐燃没有在原来的位置
while (i!=numbers[i])
    {
if (numbers[i] == numbers[numbers[i]])
      {
//重复
return numbers[i];
      }
int k = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = k;
    }
  }
return -1;
}
int main()
{
int arr[7] = { 1,2,3,4,5,2,5 };
printf("%d",duplicate(arr, 7));
return 0;
}