https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/submissions/
方法1: 数组/哈希表 时间复杂度O(n) 空间复杂度O(n)
int findRepeatNumber(int* nums, int numsSize) {
int i = 0;
int* p = (int*)malloc(numsSize * sizeof(int));
if (NULL == p) {
return 0;
}
memset(p, 0, numsSize * sizeof(int));
for (i = 0; i < numsSize; ++i) {
++p[nums[i]];
if (p[nums[i]] > 1) {
free(p);
return nums[i];
}
}
free(p);
return 0;
}
方法2: 重排序数组，交换 时间复杂度O(n) 空间复杂度O(1)
从头到尾一次扫描这个数组中的每个数字。当扫描到下标i的数字时，首先比较这个数字 == i。
如果相等，就找到了一个重复的数字（该数组在下标为i和m的位置都出现了）
如果不相等，就把第i个数字和第m数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。
int findRepeatNumber(int* nums, int numsSize){
int i = 0;
for (i = 0; i < numsSize; ++i) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
/* swap */
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return 0;
}
