3. 数组中重复的数字
题目一
- 题目描述:
长度为n的数组,所有数字都在0~n-1内。找出数组中的重复数字。如入参{2,3,1,0,2,5,3},对应重复数字为2或者3。
- 解题思路:
要求时间复杂度O(N),空间复杂度O(1)。因此不能使用排序的方法,也不能使用额外的标记数组。
对于这种数组元素在[0, n-1]范围内的问题,可以将值为i的元素调整到第i个位置上进行求解。
以(2, 3, 1, 0, 2, 5)为例,遍历到位置4时,该位置上的数为2,但是第2个位置上已经有一个2的值了,因此可以知道2重复。
- 代码:
public static boolean findDuplicateNumber1(int[] array, int[] duplications) {
if (array == null || array.length < 1) {
return false;
}
int len = array.length;
for (int i = 0; i < len; i++) {
if (array[i] < 0 || array[i] > len) {
return false;
}
}
for (int i = 0; i < len; i++) {
while (array[i] != i) {
if (array[i] == array[array[i]]) {
duplications[0] = array[i];
return true;
}
int temp = array[i];
array[i] = array[temp];
array[temp] = temp;
}
}
return false;
}
题目一
-
题目描述:长度为n+1的数组里,所有数字都在1~n的范围内,所以数组中至少有一个重复数字。请找出任意一个重复数字,但不能修改输入的数组。例如输入{2,3,5,4,3,2,6,7},对应重复数字为2或者3。
-
解题思路: 不能修改原数组,可以引入一个长度为n的辅助数组,但是这样的话空间复杂度要求O(n)。
利用二分法的概念,以中间的数字m将1~n的分为1~m和m+1~n两部分,分别统计两个范围内的数字的个数,如果1~m的数字的数目超过m,则重复数字在m中;否则m+1~n的区间里一定包含重复数字。然后继续将m+1~n的区间拆分为两份,直到找到一个重复的数字。
如数组{2,3,5,4,3,2,6,7},数字范围为1~7,分为1~4和5~7两段,1~4有5个,所以一定有重复数字;然后1~4分为1~2和3~4两段,1~2有2个,3~4有3个,所以3~4一定有重复数字;然后再分为3和4两段,3有两次,即3为重复数字。
- 代码:
public static int findDuplicateNumber2(int[] array) {
if (array == null || array.length < 1) {
return -1;
}
int start = 1;
int end = array.length - 1;
while (start <= end) {
int mid = (end - start) / 2 + start;
int count = countRange(array, start, mid); //统计范围内不同数字个数
if (end == start) { //当只统计一个数字时,如果count>1就是重复数字
if (count > 1) {
return start;
} else {
break;
}
}
if (count > (mid - start + 1)) {
end = mid;
} else {
start = mid + 1;
}
}
return -1;
}
private static int countRange(int[] array, int start, int end) {
if (array == null) {
return 0;
}
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] >= start && array[i] <= end) {
count++;
}
}
return count;
}