在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：
2 或 3
限制：
2 <= n <= 100000
方法一：直接遍历(超出时间限制)
思路：将数组中的每一个数字和后面的所有数字进行比较，当发现相等时，即为结果。
int findRepeatNumber(int* nums, int numsSize){ int i,j; for(i=0;i<numsSize;i++) { for(j=i+1;j<numsSize;j++) { if(nums[i]==nums[j]) return nums[i]; } } return -1; }
方法二：排序 + 遍历(执行用时：32 ms 内存消耗：10.5 MB)
思路：排序后能保证重复的数字连续分布，这样遍历时只需要比较当前数字和下一个数字是否相同即可。
这里需要用到C语言本身的库函数qsort–>如果不清楚的小伙伴可以看看这篇博客
int cmp(const void* a,const void* b) { return (*(int*)a-*(int*)b); } int findRepeatNumber(int* nums, int numsSize){ int i; qsort(nums,numsSize,sizeof(int),cmp); for(i=0;i<numsSize-1;i++) { if(nums[i]==nums[i+1]) return nums[i]; } return -1; }
方法三：哈希查找(执行用时：28 ms 内存消耗：10.4 MB)
思路：创建哈希数组（key:数字，value:出现次数），遍历时先检查当前索引对应的数字是否已经出现，出现则返回结果，否则更新该数字出现次数。
#define NUMS_SIZE 100000 int findRepeatNumber(int* nums, int numsSize){ int numsHash[NUMS_SIZE]={0}; for(int i=0;i<numsSize;i++) { if(numsHash[nums[i]]>0) {return nums[i];} numsHash[nums[i]]++; } return -1; }
方法四：原地排序(执行用时：24 ms 内存消耗：10.3 MB)
思路：借用输入数组，将当前索引对应的数字，替换到对应的数字索引下，保证索引和数字相等。如果出现替换时，索引和数字已经相等时，说明该数字重复，返回结果。相比于思路三的优点是不需要申请额外的空间存放Hash表。执行过程如下图。
int findRepeatNumber(int* nums, int numsSize){ int temp=0,cur=0; while(cur<numsSize) { if(nums[nums[cur]]!=nums[cur]) { temp=nums[cur]; nums[cur]=nums[temp]; nums[temp]=temp; continue; } if(cur==nums[cur]) { cur++;continue; } return nums[cur]; } return -1; }
方法五：二分法(解答错误)
根据题目发现答案在[0, n-1]中, left = 0, right = n - 1, mid = (left + right) / 2，先计算整个数组中[left, mid]范围内的数的数量，如果大于
(mid - left)，说明左侧有重复数字，right = mid，否则，left = mid，继续基于新的left, right二分。该种思路无法解决场景[0, 1, 2, 0, 4, 5, 6, 7, 8, 9]。
int Count(int* nums, int numsSize, int a, int b) { int cnt = 0; int cur = 0; while (cur < numsSize) { if (nums[cur] >= a && nums[cur] <= b) { cnt++; } cur++; } return cnt; } int findRepeatNumber(int* nums, int numsSize){ // 二分法 无法解决场景：[0, 1, 2, 0, 4, 5, 6, 7, 8, 9] int left = 0; int right = numsSize - 1; int mid, count; while (left < right - 1) { mid = (left + right) / 2; count = Count(nums, numsSize, left, mid); if (count > mid + 1 - left) { right = mid; continue; } left = mid; } if (Count(nums, numsSize, left, left) > 1) { return left; } return right; }
总结
感觉刷题的话还是要认真把每一题搞懂才行，看着力扣的大佬们都有很多中解法，也学习到了许多，我自己昨天才刚刚学到qsort函数，今天就用到了，加油吧！
