题目描述

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法

抽屉原理 $O(nlogn)$

题目描述中数是从1 - n+1的，但是nums中有n+1个数字，并且由于nums中的数字各不相同则肯定会有某一个数存在多次，这题由于这种特性可以采用二分法则和抽屉原理解答

• 将数值二分，遍历数组统计数组中数值在l - mid中的个数，如果个数小于l-mid的区间长度则在l+1 - r的区间中肯定存在重复的数字，否则在mid+1 - r中肯定有重复的数字。
• 最终l和r相同 l和r同时指向的数字就是肯定是重复的数字。

时间复杂度 $O(nlogn)$

Java 代码

public int duplicateInArray(int[] nums) {
        int l = 1, r = nums.length - 1;
        while(l != r){//l < r 也是一样的
            int mid = (l + r) >> 1;
            int s = 0;
            for(int num : nums){
                if(num >= l && num <= mid) s++;
            }
            if(s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;//return r也是一样的
    }