287寻找重复数

一、前言

标签：二分查找。

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

问题链接：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

证明，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;
}

执行结果：