ACWing-剑指Offer-不修改数组找出重复的数字

ゞ浴缸里的玫瑰 2023-07-21 08:57 19阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/15/][https_www.acwing.com_problem_content_description_15]

题目描述：

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
    
    请找出数组中任意一个重复的数，但不能修改输入的数组。
    
    样例
    给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
    
    返回 2 或 3。
    思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

算法描述：

本题只考虑利用O(1)空间的解法，对于利用Hash使得空间复杂度和时间复杂度都为![O(N)][O_N]的方法这里不考虑。

本题思路很绕（对我而言），而且会锻炼用到二分，首先给出二分模板，感谢ACWing的大佬YXC师兄给出的模型总结，大家可以关注一波ACWing网站： [https://www.acwing.com/][https_www.acwing.com]

二分模板，借鉴于ACWing

二分模板一共有两个，分别适用于不同情况。
    算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

**版本1**  
当我们将区间\[l, r\]划分成\[l, mid\]和\[mid + 1, r\]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

模板如下：

int bsearch_1(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

注意，该模板这里最后返回l，或者r都可以

**版本2**

当我们将区间\[l, r\]划分成\[l, mid - 1\]和\[mid, r\]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

int bsearch_2(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

回到该题

根据抽屉原理（鸽巢原理），我们将取值范围为1-n的这些数放到n+1个位置时，肯定会有两个位置是相同元素。那么怎么判断呢，这里用二分法的思路比较绕

1.  一般的二分都是对数组下标进行二分，即根据位置进行二分，如排序过后的数组去找中位数，或者判断是不是存在某个数等
2.  这里的二分思路则不同，我们对数字取值范围进行二分，把\[1, n\]分为\[1, n/2\]和\[n/2+1, n\]，这样的话遍历整个数组，判断每个每个数字属于上面哪两个区间，则答案就在哪个数字统计个数大于区间长度的区间内
3.  正确性不进行论证，反证法很好证

class Solution {
    public:
        int duplicateInArray(vector<int>& nums) {
            int n = nums.size();
            int l = 1, r = n;
            while (l<r)
            {
                int mid = l+r >> 1;
                int l_cnt = 0;
                for (auto num: nums) if (num>=l && num<=mid) l_cnt++;
                if (l_cnt>(mid-l+1)) r = mid;
                else l = mid + 1;
            }
            return l;
        }
    };

[https_www.acwing.com_problem_content_description_15]: https://www.acwing.com/problem/content/description/15/
[O_N]: https://private.codecogs.com/gif.latex?O%28N%29
[https_www.acwing.com]: https://www.acwing.com/