抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

数组:数组中重复的数字

题目一:找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内,数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如:如果长度为7的数组{2,3,1,0,2,5,3},那么对应输出是重复的数字2或者3。

解法一:排序

排序后找出重复的数字就只需要从头到尾遍历即可。时间复杂度为:O(nlogn)

解法二:利用哈希表

从头到尾扫数组,每扫一个都可以用O(1)的时间来判断哈希表里是否存在相同元素,没有就将其放入哈希表,存在则为一个重复数字。时间复杂度为O(N)但是代价是哈希表的空间复杂度O(N).

解法三:下标判重

数组中的数字都在0~n-1之间,如果这个数组中不存在重复的数字,那么当数组排序后,数字i就在下标为i的位置。现在是存在重复的数字,那么一个下标则可能有多个数字。

步骤分析:

以{2,3,1,0,2,5,3}为例,下标0为2,将其与下标2的数字交换,则变为{1,3,2,0,2,5,3}。此时下标0为1,也不符,则与下标1的数字交换,则为{3,1,2,0,2,5,3},按这个思路继续,直到变为{0,1,2,3,2,5,3}时,扫描到下标4,会发现其值2已经在之前交换过,此时则为重复元素。

代码:

class A {
public static void main(String[] args) {
int[] numbers = {2, 3, 1, 0, 2, 5, 3};
boolean duplicate = duplicate(numbers);
System.out.println("is duplicate:"+duplicate);
}

private static boolean duplicate(int[] numbers) {
if (numbers == null || numbers.length <= 0) {
return false;
}
for (int number : numbers) {
if (number < 0 || number > numbers.length - 1) {
return false;
}
}
//以上为判断数组是否合法 以下为主要逻辑
for (int i = 0; i < numbers.length; i++) {
//交换到numbers[i]==i才停止 停止后 for循环 i+1
while (numbers[i] != i) {
//这个条件可能不太好理解 但是你将上述文字读一遍 然后将i=4带入这个表达式就好理解了
if (numbers[i] == numbers[numbers[i]]) {
//重复
System.out.println(numbers[i]);
return true;
}
//如果不相等 则number[i]与numbers[numbers[i]]交换元素
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;

}
}
return false;
}
}

这里需要一提的是,代码中尽管有一个双重循环,但是元素交换实际上只要2次,所以最终的时间复杂度为O(N),然后操作都在输入数组上进行,不需要额外内存,空间复杂度为O(1).

题目二:不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中一定有一个数字是重复的,请找出数组中任意一个重复的数字,但不能修改输入的数组。例如:如果长度为8的数组{2,3,5,4,3,2,6,7},那么对应输出是重复的数字2或者3。

解法一:利用上一题的思路,我们创建一个新的n+1的辅助数组,然后逐一赋值到辅助数组对应下标的位置,比如第一个元素值为3,则复制到新数组的下标为3的地方,这样很容易就可以找到重复元素,但是需要O(N)的辅助空间。

解法二:尝试避免使用辅助空间。假象若没有重复的数字,那么从1~n就只有n个数字,如果取中心点m,分为1~m,与m+1到n,如果1~m的数字出现的次数超过了m,那么这里就一定有重复的数字,若无则考虑m+1~n,若有,再从中间分,依次循环。多思考下上面这句话,相信你可以理解。

以长度8的数组{2,3,5,4,3,2,6,7},根据题目要求,这个长度为8的所有数字都在1~7,中间数字是4,将这组数字分为1~4和5~7,接下来统计下1~4这几个数字在数组中出现的次数,1为0次,2为2次,3为2次,4为1次,共5次,所以这里面一定有重复数字。接下来,再分为1~2,3~4两段,数字1为0次,2为2次,共2次,数字3为2次,4为1次,共3次,则3~4则一定存在重复,接着二分为3和4按以上规律。可以得知3为重复。但是这个解法有一个问题,就是并不能准确的知道哪个是重复数字,也就是说无法找出所有重复的数字,比如说上面遗漏的数字2。这里就没有所谓的最佳解法了,按需判断即可。

代码:

class B {

public static void main(String[] args) {

int[] numbers = {2, 3, 5, 4, 3, 2, 6, 7};
int duplicate = getDuplicate(numbers);
System.out.println(duplicate);
}

private static int getDuplicate(int[] numbers) {
if (numbers == null || numbers.length <= 0) {
return -1;
}
int start = 1;
int end = numbers.length - 1;
while (end >= start) {
//位运算 防止有人看不懂 >> 1右移运算 相当于除2
int middle = ((end - start) >> 1) + start;
int middle2 = ((end - start) / 2) + start;
System.out.println("mid " + middle + " mid2: " + middle2);

int count = countRange(numbers, start, middle);
if (end == start) {
//分到最后一组 大于1则为重复 否则没有重复
if (count > 1) {
return start;
} else {
break;
}
}
if (count > (middle - start) + 1) {
//前半组 存在重复
end = middle;
} else {
//后半组存在重复
start = middle + 1;
}
}
return -1;
}

/**
* 计算该区间内数字出现的次数总和
*
*
@param numbers 数组
*
@param start 区间起始点
*
@param end 区间结束点
*
@return 数字出现的总和
*/
private static int countRange(int[] numbers, int start, int end) {
if (numbers == null) {
return 0;
}
int count = 0;
for (int number : numbers) {
//如果该数字在区间内 计数+1
if (number >= start && number <= end) {
++count;
}
}
return count;
}

}

上述解法类似二分查找,如果长度为n,则countRange的调用次数为O(logn),每次需要O(n),时间复杂度为O(nlogn),空间为O(1)。为时间换空间。

— 本题来自《剑指Offer》,仅作为自己加深印象与理解而写,书中为C++或C#,我从事Android,习惯Java,若有问题还请指出,感激不尽。


0条评论

发表评论