---

点击查看: 《剑指offer-第2版》 全部面试题 详解目录(Java版）

---

不修改数组找出重复的数字

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

• 思路一： 复制数组，按照03_01的方法手动排序。 时间O(n) 空间O(n)
• 思路二: 使用hashmap 时间O(n) 空间O(n)
• 思路三: 使用二分查找的思想，因为数字为1-n.
  • 我们把1~n的数字从中间的数字m分为两部分，前面一半为1 ~ m，后面一半为m+1 ~ n。 如果 1 ~ m的数字的数目超过m，那么这一半的区间里一定包含重复数字；否则，另一半 m+1 ~ n 的区间里一定包含重复的数字。我们可以继续把包含重复区间数字的区间一份为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。
  • 如果输入长度为n的数组，那么计数函数执行O(logn)次，每次需要O(n)的时间，因此总的时间复杂度为O(nlogn)，空间复杂度为O(1)

注意:

• start end middle 均为数组中最小值，最大值，(max-min)/2+start的值
• 目的是为了找出，某个重复的数字，故是对数组中最大和最小的数字范围进行二分 而非数组区间
  

package ch02;

/**
 * @author Ren
 */
public class T03_2_不修改数组找出重复的数字 {

    public static void main(String[] args) {
        int [] arr = {2,5,4,3,2,6,7};
        int ans = getDuplication(arr,arr.length);
        System.out.println(ans);
    }

    static int getDuplication(int [] arr, int length){
        if(arr==null || length <= 0){
            return -1;
        }
        // 找到数组中的最大值和最小值
        int min=length,max = 1;
        for (int i = 0; i < length; i++) {
            min=min>arr[i]?arr[i]:min;
            max=max<arr[i]?arr[i]:max;
        }
        int start = min;
        int end = max;
        while (end >= start){
            int middle = ((end-start)>>1) + start;
            int count = countRange(arr,length,start,middle);
            // 当start==end 则找到重复的目标，返回数据
            if(end==start){
                if(count>1){
                    return start;
                }else{
                    break;
                }
            }
            // 若 count>(middle-start+1) 该区间（数字大小区间 不是数组的区间）内有重复元素 下次循环的end=middle
            if(count>(middle-start+1)){
                end = middle;
            }else{ // 否则 对后半个区间进行统计  start = middle+1
                start = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 统计区间元素在数组中出现的次数的方法
     */
    static int countRange(int [] arr,int length,int start,int end){
        if(arr==null){
            return 0;
        }
        int counts = 0;
        for (int i = 0; i < length; i++) {
            if(arr[i]>=start && arr[i]<=end){
                counts++;
            }
        }
        return counts;
    }
}