题目：不修改数组找出重复的数字

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

分析：本题可以使用一个新数组，长度n+1，全部元素初始化为0，把原数组的每个元素根据其值放到新数组中下标对应的位置，在赋值前可以先判断当前下标位置的元素值是否为0，如果为0就赋值，不为0说明这个就是重复的元素。但是空间复杂度为O(n) ，如果用一个HashMap来存，空间复杂度也是一样。

很显然，这并不会是面试官想要的答案，面试官这时候会说如果空间复杂度为O(1)呢？

Java版本：

 private static int getOneDuplicateNumber(int[] inputArray) {
        if (inputArray == null || inputArray.length == 0 || inputArray.length == 1) {
            return -1;
        }

        int length = inputArray.length;
        int start = 1;
        int end = length - 1;

        while (end >= start) {
            int middle = (start + end) / 2;
            int countInRange = countRange(inputArray, length, start, middle);
            //分两种情况 有可能最后两个指针重合，也有可能最后两个指针相差1
            if (end == start) {
                if (countInRange > 1) {
                    return start;
                } else {
                    break;
                }
            } else if (end == start + 1) {
                if (countInRange > 1) {
                    return start;
                } else if (countRange(inputArray, length, end, end) > 1) {
                    return end;
                } else {
                    break;
                }
            }

            //二分查找，折半缩小范围
            if (countInRange <= middle) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
        return -1;
    }

    private static int countRange(int[] inputArray, int length, int start, int end) {
        if (inputArray == null) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (inputArray[i] >= start && inputArray[i] <= end) {
                count++;
            }
        }
        return count;
    }

Kotlin版本：

fun getOneDuplicateNumber(inputArray: IntArray?): Int {
    if (inputArray?.isEmpty()!!) {
        return 0
    }
    val length = inputArray.size
    var start = 1
    var end = length - 1

    while (start <= end) {
        val middle = (start + end) / 2
        val count = countRange(inputArray, start, middle)
        if (start == end) {
            if (count > 1) {
                return start
            } else {
                break
            }
        } else if (start + 1 == end) {
            return if (count > 1) {
                start
            } else if (countRange(inputArray, end, end) > 1) {
                end
            } else {
                break
            }
        }

        if (count <= middle) {
            start = middle + 1
        } else {
            end = middle
        }
    }
    return -1
}


fun countRange(inputArray: IntArray?, start: Int, end: Int): Int {
    if (inputArray?.isEmpty()!!) {
        return 0
    }
    var count = 0
    inputArray.forEach {
        if (it in start..end) {
            count++
        }
    }
    return count
}

包含测试的完整代码：https://github.com/chenyucheng97/CodeingInterviews