题目
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字。例如：如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3。
分析
暴力法
先排序再查找重复，时间复杂度O(nlg(n))，空间复杂度为O(1)。
#include<stdio.h> #include<stdlib.h> int compar_int(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; } int getDuplication(int a[], int n) { int ret = -1; qsort(a, n, sizeof(a[0]), compar_int); //排序 for (int i = 0; i < n - 1; i++) //查找 { if (a[i] == a[i + 1]) { ret = a[i]; break; } } return ret; } int main() { int arr[7] = { 2,3,4,0,2,5,3 }; int len = sizeof(arr) / sizeof(arr[0]); int ret = getDuplication(arr, len); printf("任意一个重复的元素是：%d\n", ret); return 0; }
哈希表法
我们可以遍历一次，以值为key，出现的次数为value，然后以数组建立哈希表。这样可以使时间复杂度降为O(n),空间复杂度为O(n);这是典型的拿空间换时间。
c
#include<stdio.h> #include<stdlib.h> int getDuplication(int a[], int n) { int* tmp = (int*)calloc(n, sizeof(n));//创建数组空间并初始化为0 int ret = -1; if (NULL == tmp) { perror("tmp空间开辟失败！"); exit(EXIT_FAILURE); } for (int i = 0; i < n; i++) { if (1 == tmp[a[i]])//之前出现过一次 { ret = i; } tmp[a[i]]++; } free(tmp);//回收空间 tmp = NULL; return ret; } int main() { int arr[7] = { 2,3,4,0,2,5,3 }; int len = sizeof(arr) / sizeof(arr[0]); int ret = getDuplication(arr, len); if (-1 == ret) { printf("没有重复的元素！"); } else { printf("任意一个重复的元素是：%d\n", ret); } return 0; }
c++
#include<iostream> #include<vector> #include<map> using namespace std; class Solution { public: int getDuplication(vector<int>& nums) { map<int, int> map;//<值，出现次数> int ret = -1; for (int num : nums) { if (map[num] == 1)//如果出现过一次，就退出 { ret = num; break; } map[num]++; } return ret; } }; int main() { vector<int>arr{ 2,3,4,0,2,5,3 }; Solution s; int ret = s.getDuplication(arr); cout<<"任意一个重复的元素是："<< ret ; return 0; }
原地交换法
我们注意到数组中的数字都在0~n-1的范围内，如果这个数组中没有重复的数字，那么当数组排序之后数字i会在下表为i的位置上。因为有重复数字，所以必然会存在有些位置可能存在多个数字，有些位置可能没有数字。
从头到尾一次扫描这个数组中的，如果发现下表i与其value不同，就将其value下标的值与当前值交换，直到找出俩边的value相同为止。
缺点就是会修改数组的数据。
下面为图解：
#include<stdio.h> void swap(int a[], int v1, int v2) { int tmp = a[v1]; a[v1] = a[v2]; a[v2] = tmp; } int getDuplication(int a[], int n) { int ret = -1; int i = 0; if (a == NULL || n <= 0) //判断特殊情况 { return ret; } while(i < n) { if (i != a[i]) //value与i不相等 { if (a[a[i]] == a[i]) //找到相同俩个值 { ret = a[i]; break; } swap(a, i, a[i]); //交换函数 } else { i++; } } return ret; } int main() { int arr[7] = { 2,3,1,0,2,5,3 }; int len = sizeof(arr) / sizeof(arr[0]); int ret = getDuplication(arr, len); if (-1 == ret) { printf("没有重复的元素！"); } else { printf("任意一个重复的元素是：%d\n", ret); } return 0; }
题目增加要求
现在要求不能修改数组本身。题目不变。
例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7};那么对应输出是重复的数字2或者3.
思路
虽然我们可以自己创建一个辅助数组来进行查找，但是空间复杂度就成了O(n)；
我们仔细想，为什么会有重复元素，因为范围小于个数，所以必然有重复元素，那么我们可以一直缩小范围来找这个值。用二分法来查找区间
思路如下：
C
#include<stdio.h> #include<assert.h> int countRange(const int arr[], int length, int start, int end) { assert(arr != NULL); assert(length > 0); int count = 0; for (int i = 0; i < length; i++) { if (arr[i] <= end && arr[i] >= start) { count++; } } return count; } int getDuplication(const int arr[], int length) { assert(arr != NULL); assert(length > 0); int ret = -1; //存储重复元素的值 int start = 1; //范围下限 int end = length - 1; //范围上限 while (start <= end) { int mid = ((end - start) >> 1) + start; //防止溢出 位移运算速度快 int count = countRange(arr, length, start, mid);//先统计前区域 if (count > (mid - start + 1)) //该区域有重复元素 { end = mid; } else { start = mid + 1; //因为mid被算在前区域，所以这边必须+1 } if (start == end) { if (count > 1) //确保是找到俩个或者以上相同的元素 { ret = arr[start]; } break; } } return ret; } int main() { //int arr[8] = { 2,3,5,4,3,2,6,7 }; int arr[8] = { 2,2,3,4,5,5,6,7 }; int length = sizeof(arr) / sizeof(arr[0]); int ret = getDuplication(arr,length); if (-1 == ret) { printf("未找到重复元素！"); } else { printf("找到的重复元素为：%d\n", ret); } return 0; }
本章完
