在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入:[2,3,1,0,2,5,3] 输出:2或3 //数组长度为7,重复的只有2和3,因此任意输出一个结果都是正确的思路①
- 利用长度为n的数组arr记录某个数字的出现次数,数组下标与数字一一对应【如数字0就由arr[0]记录其出现的次数】,当统计的个数超过1时就将此下标输出。
- 时间复杂度O(n),空间复杂度O(n)
public static void duplicate(int numbers[]) {
int n = numbers.length;
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
int index=numbers[i]; //当前数字出现次数信息存储在arr[index]
arr[index]++;
if(arr[index]==2) { //当次数等于2时,说明index就是重复数
System.out.println(index);
break;
}
}
}
思路②
- 由于数组中的数字都处于0~n-1范围内,如果数组中没有重复的数,那么当数组排序之后数组i将出现在下标为i的位置。
- 因此我们的新思路为“将每个数摆到属于自己的地方”
- 首先比较这个数字是不是等于当前扫描到的下标,如果是则说明其处于正确位置,继续往后扫描;如果不是,则将此数字送到属于自己的下标位置。
- 若此时发现下标位置已被正确占领,则说明此数字重复,输出此数;反之则进行对调,再重复进行判断。
- 时间复杂度O(n),空间复杂度O(1)
public static void duplicate(int numbers[]) {
int n = numbers.length;
int temp;
for (int i = 0; i < n; i++) {
while (numbers[i] != i) {// 此时说明当前数字处于错误位置
int index = numbers[i]; // 正确的位置下标为index
if (numbers[index] == index) {
// 正确的位置已经名花有主,说明这个位置存放的数就是重复的
System.out.println(index);
i=n; //使函数跳出for循环
} else {
temp = numbers[index];
numbers[index] = numbers[i];
numbers[i] = temp;
}
}
}
}
题目二:不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。
输入:[2,3,5,4,3,2,6,7] 输出:2或3 //数组长度为8,重复的只有2和3,因此任意输出一个结果都是正确的思路①
- 可参考题目一中的思路①,用辅助数组对各个数字的出现次数进行统计。
- 在1~n的范围里只有n个数字,而数组空间有n+1个,所以一定有重复数
- 我们可以采用二分法的思想,把1~n的数字从中间的数字m分为两部分,前面一半为1~m,后面一半为m+1~n。如果数组里1~m的数字个数超过m,则重复的数字肯定会出现在1~m这个区间里【但这并不代表另一个区间就没有重复数字,只是题目仅要求我们找出任意重复数字即可】,否则出现在另一个区间里。
- 通过不断缩小区间范围,最后我们确定下一个重复的数字
- 时间复杂度O(nlogn),空间复杂度O(1)
public static int duplicate(int numbers[]) {
int n = numbers.length-1 ; // 数组内存放数字范围1~n,数组空间有n+1个,下标从0到n
int left = 1, right = n;
while (left <= right) {
int m = (left + right) / 2; // left~right的中间数
// [left,m]范围的数字在数组中出现的次数
int count = getCountNum(numbers, left, m);
if (left == right) { // 说明此时二分已经将范围缩小到最后一个数字
if (count == 1) {
// 此时说明当前数字在数组中出现的次数为1次,整个数组没有重复数
break;
} else {
// 此时说明最终定位到的就是重复数
return left;
}
}
if (count > m - left + 1) {
// [left,m]范围数字出现的次数多于这个范围数字一一对应时的数目
// 此时在此范围肯定出现了重复数
right = m;
} else {
// 在另一个范围出现了重复数
left = m + 1;
}
}
return -1;
}
// 返回[left,right]范围的数字在numbers[]数组中出现的次数
public static int getCountNum(int numbers[], int left, int right) {
int count = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] >= left && numbers[i] <= right) {
count++;
}
}
return count;
}
题目虽然看上去不难,但是其中细节还是挺多的,建议手动进行实现!
题目来源于《剑指Offer:名企面试官精讲经典编程题(第2版)》



