剑指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;
}
}
