《剑指offer第二版》面试题3 题目二：不修改数组找出重复的数

题目描述

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

题目分析

1. 以长度为8的数组{2,3,5,4,3,2,6,7}为例。这个长度为8的数组里所有数字都在1-7范围内。
2. 中间的数字4把数组分为两个部分，1 ~ 4,和5 ~ 7。
3. 计算数组中1 ~ 4范围内的数字共有5个，说明1 ~ 4内有重复数字。
4. 1 ~ 4的中间数字2将1 ~ 4的数字分为两个部分，1 ~ 2和3 ~ 4。
5. 1 ~ 2的数字有2个，3 ~ 4的数字有3个，因此3 ~ 4的数字内有重复数字。
6. 3 ~ 4的中间数字3将3~4之间的数字分为两个部分3 ~ 3和4~4 。
7. 3~3的数字共有2个，则找到了重复数字3。

代码

int getDuplicate(int[] arr){
    if (arr == null || arr.length <= 0) {
        return -1;
    }

    int start = 1;
    int end = arr.length - 1;
    while (start <= end) {
        int middle = start + (end - start) / 2; // 找出中间数字
        int count = countRangeNumbers(arr, start, middle); // 计算start~middle中数字的个数
        if (start == middle) {
            if (count > 1) { // 如果数量大于1，说明该数字重复了
                return start;
            } else {
                break;
            }
        }
        if (count > (middle - start + 1)) {
            // 如果start~middle中数字的个数大于start和middle的差值，说明这段数字有重复的
            end = middle - 1;
        } else {
            // 如果start~middle中数字的个数小于start和middle的差值，说明这段数字没有有重复的
            start = middle + 1;
        }
    }
    return -1;
}

/**
 * 求数组里在start~end范围内的数字的个数
 */
int countRangeNumbers(int[] arr, int start, int end) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] >= start && arr[i] <= end) {
            count ++;
        }
    }
    return count;
}