剑指Offer面试题：6.不修改数组找出重复的数字
一、题目
————————————————
在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
————————————————
二、思路
————————————————
方法一：数组长度为n+1，而数字只从1到n，说明必定有重复数字。可以由二分查找法拓展：把1n的数字从中间数字m分成两部分，若前一半1m的数字数目超过m个，说明重复数字在前一半区间，否则，在后半区间m+1~n。每次在区间中都一分为二，知道找到重复数字。
更简单的思路：把该数组看作一个链表，下标代表当前结点，值代表next指针，具体参考Find the Duplicate Number，时间复杂度仅为O(n)
————————————————
三、解决问题
————————————————
测试用例
1.数组中带一个或多个重复数字
2.数组中不包含重复的数字
3.无效输入测试用例（空数组，数组数字越界等）
————————————————
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-13 10:09
*/
import java.util.HashMap;
import java.util.Objects;
/**
* 题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至
* 少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的
* 数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的
* 输出是重复的数字2或者3。
*/
public class Solution06 {
public static void main(String[] args) {
System.out.println("==============================");
Solution06 sword = new Solution06();
sword.test1();
System.out.println("==============================");
sword.test2();
System.out.println("==============================");
sword.test3();
System.out.println("==============================");
}
/**
* 方法二：（类似二分法）
* 时间复杂度：O(nlogn) （while循环为O(logn)，coutRange()函数为O(n)）
* 空间复杂度：O(1)
* 可以由二分查找法拓展：把1~n的数字从中间数字m分成两部分
* 若前一半1~m的数字数目超过m个，说明重复数字在前一半区间
* 否则，在后半区间m+1~n。
* 每次在区间中都一分为二，知道找到重复数字。
* @param array
* @return
*/
public int getDuplicate01(int[] array) {
if(null == array || array.length <= 0){
System.out.println("数组输入无效！");
return -1;
}
//保证数组长度为n+1，而数字只从1到n，说明必定有重复数字
for(int arr : array){
if(arr < 1 || arr > array.length - 1){
System.out.println("数字大小超出范围！");
return -1;
}
}
int low = 1;
int high = array.length - 1;// high即为题目的n
int mid,count;
while(low <= high){
//把1~n的数字从中间数字m分成两部分，
mid = ((high - low) >> 2) + low;
count = countRange(array,low,mid);
if(low == high){
if(count > 1){
return low;
}else{
break;// 必有重复，应该不会出现这种情况吧？
}
}
if(count > mid - low + 1){
high = mid;//若前一半1~m的数字数目超过m个，说明重复数字在前一半区间
}else{
low = mid + 1;//否则，在后半区间m+1~n。
}
}
return -1;
}
/**
* 方法二：构建一个哈希表，遍历数组所有数字
* 判断哈希表中是否存在这个数字:
* 如果没有，则添加进哈希表。如果已经存在，则输出该值。
* @param array
* @return
*/
public int getDuplicate02(int[] array) {
if(null == array || array.length <= 0){
System.out.println("数组输入无效！");
return -1;
}
//保证数组长度为n+1，而数字只从1到n，说明必定有重复数字
for(int arr : array){
if(arr < 1 || arr > array.length - 1){
System.out.println("数字大小超出范围！");
return -1;
}
}
//新建一个hashmap
HashMap<Integer, Integer> hashMap = new HashMap<>();
//遍历数组中的元素
for (int i = 0; i < array.length; i++) {
if(! hashMap.containsKey(array[i])){
//如果hash表中没有该数字，添加并以其本身作为关联键
hashMap.put(array[i],array[i]);
}else{
//如果存在该数字了，说明出现重复数字，则返回该数字
return array[i];
}
}
return -1;
}
/**
* 返回数组元素在[low,high]范围中出现个数
*/
public int countRange(int[] array, int low, int high) {
if(null == array){
return 0;
}
int count = 0;
for(int arr : array){
if(arr >= low && arr <= high){
count++;
}
}
return count;
}
// ==================================测试代码==================================
/**
*数组为null
*/
public void test1() {
System.out.println("test1：");
int[] a = null;
System.out.println("方法一：");
int dup = getDuplicate01(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
dup = 0;
System.out.println("方法二：");
dup = getDuplicate02(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
}
/**
*数组数字越界
*/
public void test2() {
System.out.println("test2：");
int[] a = { 1, 2, 3, 4 };
int dup = getDuplicate01(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
dup = 0;
System.out.println("方法二：");
dup = getDuplicate02(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
}
/**
*数组带重复数字
*/
public void test3() {
System.out.println("test3：");
int[] a = { 1, 2, 3, 2, 4 };
int dup = getDuplicate01(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
dup = 0;
System.out.println("方法二：");
dup = getDuplicate02(a);
if (dup >= 0){
System.out.println("重复数字为：" + dup);
}
}
}
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
Java基础 文章被收录于专栏
建立本人的Java基础技术栈积累库
投递杉川机器人等公司10个岗位
查看16道真题和解析
