Keshawn_lu's Blog

Leetcode 287. 寻找重复数

二分查找
字数统计: 700阅读时长: 2 min
2020/05/26 Share

题目简介：

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

示例 1:

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

示例 2:

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

说明：

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

思路：

由于说明中的要求过多，所以不能按照普通的方法来做，所以想到使用二分的方法。

每次先算出中位数mid，然后求原始数组中小于等于mid的个数，如果数量count超过了mid，则说明重复的数字出现在[left, mid]中，否则，则出现在[mid + 1, right]中。

以 [2, 4, 5, 2, 3, 1, 6, 7] 为例，一共 8 个数，n + 1 = 8，n = 7，根据题目意思，每个数都在 1 和 7 之间。

例如：区间[1, 7]的中位数是 4，遍历整个数组，统计小于等于 4 的数字的个数，若[1, 4]区间内不会重复，则该区间内数字的个数最多为 4 个(如[1,2,3,4])。如果整个数组里小于等于 4 的整数的个数大于 4 个，就说明重复的数存在于区间 [1, 4]。然后使right = mid，进行下一轮。

这个例子中，小于等于 4 的个数为 5 个，令right = 4，开始第二轮，新区间为[1, 4]。

第二轮时，中位数mid = 2，小于等于2的个数为 3 个，大于mid = 2，所以令right = 2，开始第三轮，新区间为[1, 2]。

第三轮时，中位数mid = 1，小于等于1的个数为 1 个，等于mid，所以令left = mid + 1 = 2，此时left == right，返回left == 2即为重复的数字。

tip:

  • 如果整个数组里小于等于 mid 的数字的个数等于mid，在区间[left, mid]也不会有重复数字，如上述例子中，若小于等于 4 的数字的个数为 4 个且存在重复([1,2,4,4])，由于数组的总长度为 8 ，且数字只能出现在[1, 7]内，所以剩余的数字[5, 6, 7]是不可能有8 - 4 = 4个的，不然必会有第二个数字重复，与题意不符。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        int left = 0;
        int right = nums.size() - 1;

        while(left < right){

            int mid = left + (right - left) / 2;    //防溢出

            int count = 0;
            for(int num : nums){

                if(num <= mid)
                    count++;
            }

            if(count > mid)
                right = mid;
            else
                left = mid + 1;
        }

        return left;

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网