一.题目一
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
例如：
输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3
二.思路
- 运用哈希表不重复的特点，扫描数组，扫描得到的元素不在哈希表中，则把该元素放入哈希表，继续扫描；若扫描到的元素在哈希表中，则该元素为重复元素，返回该元素；
- 上述方法很简单，但是空间复杂度为O(n)，考虑是不是能把空间复杂度降低一下？我们发现数组里面的所有数字都在0~n-1 的范围内，所以有如下想法：把数组重排的话，如果不重复，那么位置为i的元素大小应该也为i,如果有重复元素，位置为i的元素应该至少有两个元素，也就是出现了碰撞。因此我们决定重排数组，把元素放到对应的位置，一旦出现碰撞，则出现重复。
三.代码
方法一代码：
//unordered_map bool duplicate(int numbers[], int length, int* duplication){ unordered_map<int,int> umap; if(numbers == nullptr || length <= 0) return false; for(int i = 0;i < length;i++) if(numbers[i] < 0 || numbers[i] > length - 1) return false; for(int i = 0;i < length;i++){ if(!umap.count(numbers[i])){ *duplication = numbers[i]; return true; } umap[numbers[i]] = i; } return false; }
方法二代码：
//collision bool duplicate(int numbers[], int length, int* duplication){ if(numbers == nullptr || length <= 0) return false; for(int i = 0;i < length;i++) if(numbers[i] < 0 || numbers[i] > length - 1) return false; for(int i = 0;i < length;i++){ while(numbers[i] != i){ if(numbers[i] == numbers[numbers[i]]){ *duplication = numbers[i]; return true; } int tmp = numbers[i]; numbers[i] = numbers[tmp]; numbers[tmp] = tmp; } } return false; }
四.本题考点
- 考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应元素。
- 考查应聘者分析问题的能力。当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，是能否解决这个问题的关键所在。
五.题目二
在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
例如，
如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
六.思路
- 考虑一个辅助数组，同样采用题目一的方法二，只不过这次是在辅助数组上做操作
- 上述方法空间复杂度为O(n)，我们同样考虑如何降低空间复杂度。可以考虑二分查找的思路：我们把1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n。如果前面1~m部分的数字的数目超过m，那么这一部分一定包含重复的数字；否则，另一半m+1~n的部分必定包含重复数字。我们可以把包含重复数字的部分继续一分为二，直到找到一个重复的数字。在这个过程中，我们要加一个子函数，计算某一部分里数字的部分。
七.代码
方法一代码
int getDuplication(const int* numbsers,int length){ if(numbers == nullptr || length <= 0) return false; int tmp[length]; for(int i = 0;i < length; i++){ if(numbers[i] < 1 || numbers[i] > length) return 0; if(tmp[i]) return 1; tmp[i] = numbers[i]; } return 0; }
方法二代码
int getDuplication(const int* numbers,int length){ if(numbers == nullptr || length < 0) return 0; int start = 0; int end = length - 1; while(start <= length){ int mid = start + ((end - start) >> 1); int count = countRange(numbers,length,start,mid); if(start == end){ if(count > 1) return start; else return -1; } if(count > (mid - start + 1)) end = mid - 1; else start = mid + 1; } return -1; } int countRange(int* numbers,int length,int start,int end){ if(numbers == nullptr) return 0; int count = 0; for(int i = start;i < end;i++){ if(numbers[i] >= start && numbers[i] <= end) ++count; } return count; }
八.本题考点
- 考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。
- 考查应聘者对二分查找算法的理解，并能快速、正确的实现二分查找算法的代码
- 考查应聘者的沟通能力。应聘者只有具备良好的沟通能力，才能充分了解面试官的需求，从而有针对性的选择算法解决问题。