Leetcode-287-寻找重复数字

Leetcode-287-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

说明：

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

Solution：二分法

• 如果测试数据不在这个范围里，二分法失效。

• 二分法的常见作用：可以用来确定一个有范围的整数

• 预备知识：

抽屉原理：假设要把10个苹果放进9个柜子，那么一定有一个柜子放了不止一个。

容易想到的方法有：

• 使用哈希表判重，这违反了限制 2；
• 将原始数组排序，排序以后，重复的数相邻，即找到了重复数，这违反了限制 1；
• 使用类似「力扣」第 41 题：缺失的第一个正数 （原地哈希）的思路，当两个数发现要放在同一个地方的时候，就发现了这个重的元素，这违反了限制 1；
• 既然要定位数，这个数恰好是一个整数，可以在「整数的有效范围内」做二分查找，但是比较烦的一点是得反复看整个数组好几次，本题解就介绍通过二分法定位一个有范围的整数；
• 还可以使用「快慢指针」来完成，不过这种做法太有技巧性了，不是通用的做法，可以查看官方题解。

思路：

• 二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid）

• 然后统计原始数组中小于等于这个中间数的元素的个数 count , 如果count 严格大于 mid ，注意我加了着重号的部分「小于等于」、「严格大于」）。

• 根据抽屉原理，重复的元素就在区间 [left, mid] 里；

举个例子：

• 以[2,4,5,2,3,1,6,7] 为例，一共 8 个数，n + 1 = 8 那么 n = 7 并且根据题目的意思，每个数都在[1,7]之间
• 例如：区间[1,7]的中位数是4
  • 之后遍历整个数组，统计小于等于4的整数的个数，如果不存在重复元素，最后就是4个。
  • 等于4的时候区间[1,4]内也可能有重复的元素，比如 [1,2,2,4] 。
  • 但是,如果整个数组里小于等于4的正数的个数严格大于4 的时候，根据抽屉原理，一定说明重复的数字在[1,4]之间。

Java

Solution :

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;

        int left  = 1;
        int right = len - 1;

        while (left < right){
            //在 Java 里可以这么用，
            // 当 left + right 溢出的时候，无符号右移保证结果依然正确
            int mid = (left + right) >>> 1;

            // 每次更新 count 会被重置为0
            int count = 0;

            // 统计原始数组中小于等于这个中间数元素的个数count
            for (int num : nums) {
                if (num <= mid){
                    count += 1;
                }
            }

            // 根据抽屉原理，count如果严格大于mid个
            // 此时重复元素一定在[1,mid]之间
            if (count > mid){
                // 重复元素位于[left,mid]之间
                right = mid;
            }else {
                // 重复元素位于[mid + 1, right] 之间
                left = mid + 1;
            }
        }
        // left = right 的时候推出循环，结果就是重复的数字
        return left;
    }
}

• 时间复杂度：O(nlogn) - 二分法的时间复杂度是O(logn) ,并且在二分法内部执行了一次 for 循环 ，时间复杂度是O(n), 所以总的复杂度是O(nlogn)。
• 空间复杂度O(1) : 使用了一个count变量

测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.findDuplicate(new int[]{2, 4, 5, 2, 3, 1, 6, 7}));
}

打赏