一、题目
————————————————
在一个长度为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);
        }
    }
}

图片说明
————————————————
努力也是需要学习的,别再让你的努力,只感动了自己!愿你的每一次努力,都能为自己和别人创造价值。