剑指offer03:数组中重复的数字
题目
题目链接
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
分析
首先本题要清楚题目的要求:
- 先对数组进行排序,然后再查找排序后的数组中的重复元素
public class Solution {
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || length <= 0) {
return false;
}
Arrays.sort(numbers);
for (int i = 0; i < length - 1; i++) {
if (numbers[i + 1] == numbers[i]) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}
-
从头到尾依次扫描数组中每一个数字。当扫描到第i个元素时,比较该位置数值m是否等于i。若是,接着扫描下一个数字;否则,将其与第m个数字进行比较。若相等,则返回该重复数字;否则,交换两个数字,继续重复前面的过程。
数组的长度为 n 且所有数字都在 0 到 n-1 的范围内,我们可以将每次遇到的数进行"归位",当某个数发现自己的"位置"被相同的数占了,则出现重复。
扫描整个数组,当扫描到下标为 i 的数字时,首先比较该数字(m)是否等于 i,如果是,则接着扫描下一个数字;如果不是,则拿 m 与第 m 个数比较。如果 m 与第 m 个数相等,则说明出现重复了;如果 m 与第 m 个数不相等,则将 m 与第 m 个数交换,将 m "归位",再重复比较交换的过程,直到发现重复的数举个栗子:
以数组 {2,3,1,0,2,5,3} 为例
当 i = 0 时,nums[i] = 2 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{1,3,2,0,2,5,3}
此时 i = 0,nums[i] = 1 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{3,1,2,0,2,5,3}
此时 i = 0,nums[i] = 3 != i,判断 nums[i] 不等于 nums[nums[i]],交换 nums[i] 和 nums[nums[i]],交换后数组为:{0,1,2,3,2,5,3}
此时 i = 0,nums[i] = 0 = i,继续下一组
当 i = 1,nums[i] = 1 = i,继续下一组
当 i = 2,nums[i] = 2 = i,继续下一组
当 i = 3,nums[i] = 3 = i,继续下一组
当 i = 4,nums[i] = 2 != i,判断 nums[i] 等于 nums[nums[i]],出现重复,赋值返回
public class Solution {
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || length <= 0) {
return false;
}
for (int i = 0; i < length; i++) {
while (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
}
return false;
}
}
- 利用 HashSet或辅助数组 解决,从头到尾扫描数组,每次扫描到一个数,判断当前数是否存在 HashSet 中,如果存在,则重复,对 duplication 赋值返回,否则将该数加入到 HashSet 中。
public class Solution {
//利用 HashSet 解决,从头到尾扫描数组,每次扫描到一个数,判断当前数是否存在 HashSet 中,如果存在,
//则重复,对 duplication 赋值返回,否则将该数加入到 HashSet 中
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || length <= 0) {
return false;
}
Set set = new HashSet();
for (int i = 0; i < numbers.length; i++) {
if (set.contains(numbers[i])) {
duplication[0] = numbers[i];
return true;
}else {
set.add(numbers[i]);
}
}
return false;
}
}
扩展:
在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。从数组中找出任意一个重复的数字,但不能修改输入的数组。如{2,3,5,4,3,2,6,7}得到2或者3.
- 在数字
1
~n
中取中间值m
= (1+n) / 2, 此时数字包括1
~m
,m+1
~n
两段;
遍历数组,获得数字1
~m
的个数;
如果数字1
~m
的个数大于m
,说明1
~m
这一段内肯定有重复数字,那么在这一段内继续取中间值比较;
如果数字1
~m
的个数等于m
,这一段不一定有重复数字,比较后一段;
如果数字1
~m
的个数小于m
,说明m+1
~n
这一段一定有重复数字,在后一段取中间值比较;
按照上述方法一直取中间值比较,直到只剩一个数字且这个数字出现次数超过 1 ,该数字即为重复数字
public class Other {
/**
*
* 1)把1~n的数字从中间的数字m分为两部分,前面一半为1~m,后面一半为m+1~n
*
* 2)如果1~m这部分的数字对应数组里的值超过m个,这个区间就包含有重复的数字,否则就是另外一个区间包含重复的数字。就算两个区间都有重复的也只要再对某一个区间进行二分,因为题目要求只要找到任意一个重复的数字
*
* 3)继续把重复数字的区间进行二分,直到找到一个重复的数字
*/
/**
* int mid = (start+end)/2可能会溢出,用>>是遇到负奇数的时候求上下界统一
* -5/2=-2 5/2=2 上下界求法不统一
* -5>>1=-3 5>>1=2 统一
*/
int getDuplication(int[] numbers, int length) {
int start = 1;
int end = length - 1;
while (end >= start) {
int mid = start + (end - start) >> 1;
int count = countRange(numbers, length, start, mid);
if (end == start) {
if (count > 1) {
return start;
}
break;
}
if (count > (mid - start + 1)) {
end = mid;
} else {
start = mid + 1;
}
}
return -1;
}
int countRange(int[] numbers, int length, int start, int end) {
int count = 0;
for (int i = 0; i < length; i++) {
if (numbers[i] >= start && numbers[i] <= end) {
++count;
}
}
return count;
}
}
Q.E.D.
Comments | 0 条评论