287寻找重复数

阳光穿透心脏的1/2处 2023-03-01 12:42 4阅读 0赞

## 一、前言 ##

标签：二分查找。

问题来源LeetCode 287 难度：中等。

问题链接：[https://leetcode-cn.com/problems/find-the-duplicate-number/][https_leetcode-cn.com_problems_find-the-duplicate-number]

## 二、题目 ##

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

**示例1:**

输入: [1,3,4,2,2]
    输出: 2

**示例2:**

输入: [3,1,3,4,2]
    输出: 3

**说明：**

不能更改原数组（假设数组是只读的）。
    只能使用额外的 O(1) 的空间。
    时间复杂度小于 O(n2) 。
    数组中只有一个重复的数字，但它可能不止重复出现一次。

## 三、思路 ##

题意要求空间复杂度是O(1)，如果没有这个要求，一次遍历即可。为满足要求，再看一次题意，\[给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数\]，第一次看题一扫而过没有正确理解题意。

1.  按照题意就是数组a\[i\]，1 <= i <= n && 1 <= a\[i\] <=n，其中有且只有一个数出现多次。那可以转换一下 a\[i\] 记录 数字 i 出现的次数，现在需要找到 k 需要满足 a\[k\] > 1。
2.  我们在1-n之间随便选取一个值m，k包含在\[1,m\] 或者包含在\[m+1,n\]之间，包含在哪一个是无所谓的，如果包含在\[1,m\]，那么sum(a\[1,m\]) > m，反之在包含在\[m+1,n\]之间。
3.  通过步骤2，我们可以缩小k所在的区间，一直执行步骤2，直到区间无法缩小，也就可以确定k值了。

对于步骤二中缩小区间可以用二分查找法，接下来需要证明：如果包含在\[1,m\]，那么sum(a\[1,m\]) > m

![20200725225335109.png][]

证明，k包含在\[i,m\]，sum(a\[1,m\]) > m。

1.  假设a\[k\] = 2，那么除了a\[k\]以外所有数都是出现一次，则 sum(a\[1,m\]) = m+1，满足 sum(a\[1,m\]) > m
2.  假设a\[k\] = 3，那么除了a\[k\]以外会有一个数出现0次，如果出现0次的数大于m，则 sum(a\[1,m\]) = m+2，满足 sum(a\[1,m\]) > m；如果出现0次的数不大于m，则 sum(a\[1,m\]) = m+1，满足 sum(a\[1,m\]) > m。最终结果满足 sum(a\[1,m\]) > m
3.  假设a\[k\] > 3，那么除了a\[k\]以外会有多个数出现0次，如果出现0次都不大于m，则 sum(a\[1,m\]) = m+2，满足 sum(a\[1,m\]) > m；如果有h个数出现0次的数大于m，则 sum(a\[1,m\]) = m+1 + h，满足 sum(a\[1,m\]) > m。最终结果满足 sum(a\[1,m\]) > m
4.  所以a\[k\] > 2, 满足k包含在\[i,m\]，sum(a\[1,m\]) > m

## 四、总结 ##

*  本题题意\[给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）\]需要看明白，论看题重要性哈哈哈。
 *  本题很巧妙的运用题意中的规则。

## 五、编码实现 ##

//==========================================================================
    /*
    * @file    : 287_FindDuplicate.h
    * @label   : 二分查找
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107586568
    * @author  : niebingyu
    * @date    : 2020/07/25
    * @title   : 287.寻找重复数
    * @purpose : 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
    * 可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
    *
    * 示例 1:
    *   输入: [1,3,4,2,2]
    *   输出: 2
    *
    * 示例 2:
    *   输入: [3,1,3,4,2]
    *   输出: 3
    *
    * 说明：
    *   不能更改原数组（假设数组是只读的）。
    *   只能使用额外的 O(1) 的空间。
    *   时间复杂度小于 O(n2) 。
    *   数组中只有一个重复的数字，但它可能不止重复出现一次。
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <deque>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_FINDDUPLICATE namespace NAME_FINDDUPLICATE {
    #define NAMESPACE_FINDDUPLICATEEND }
    NAMESPACE_FINDDUPLICATE
    
    class Solution 
    {
    public:
        int findDuplicate(vector<int>& nums) 
        {   
            int n = nums.size();
            int l = 1, r = n - 1, ans = -1;
    
            while (l <= r) 
            {
                int mid = (l + r) >> 1;  
                int cnt = 0;
                for (int i = 0; i < n; ++i) 
                {
                    //遍历数组 若数组中的值 小于mid 累加bool值 到cnt中
                    cnt += nums[i] <= mid;
                }
    
                //如果累加后 小等于 mid 的个数 小等于 mid  
                //那说明 数组中 小等于mid值的 元素 不存在重复的
                //更新左边界
                if (cnt <= mid) 
                    l = mid + 1; 
                //否则说明 有重复元素
                else 
                {
                    r = mid - 1; //更新右边界
                    ans = mid; //且保存当前 mid值 因为当前mid就有可能是重复元素
                }
            }
            return ans;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int expect)
    {
        Solution s;
        int result = s.findDuplicate(nums);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums = { 1,3,4,2,2 };
        int expect = 2;
        test("Test1()", nums, expect);
    }
    
    NAMESPACE_FINDDUPLICATEEND
    // 测试 用例 END
    //
    void FindDuplicate_Test()
    {
        cout << "------ start 287.寻找重复数 ------" << endl;
        NAME_FINDDUPLICATE::Test1();
        cout << "------ end 287.寻找重复数 --------" << endl;
    }

**执行结果：**

![20200725225522653.png][]

[https_leetcode-cn.com_problems_find-the-duplicate-number]: https://leetcode-cn.com/problems/find-the-duplicate-number/
[20200725225335109.png]: /images/20230208/5c4a9faaeef14728a28cf5b3ea835f14.png
[20200725225522653.png]: /images/20230208/955ec07a69474804bb6fa5595648e018.png