题目描述

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

算法1

思路： 抽屉原理，n+1个抽屉放n个苹果，肯定有一个抽屉需放两编号相同的

对应题目，意味着左半边的或是右半边的苹果数比其长度多1

方法：二分查找

时间复杂度 O(nlog(n))

参考文献

acwing 剑指offer

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

        int l = 1, r = nums.size() - 1;  //这里需注意，l,r 代表的是苹果编号

        while (l < r)
        {
            int mid = l + r >> 1;
            int s = 0;
            for (auto x : nums) s += x >= l && x <= mid;
            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return r;

    }
};