Leetcode题目287.寻找重复数（中等）

题目描述：

给定一个包含 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) 。

数组中只有一个重复的数字，但它可能不止重复出现一次。

思路分析：

关键：这道题的关键是对要定位的“数”做二分，而不是对数组的索引做二分。要定位的“数”根据题意在 1 和 n 之间，每一次二分都可以将搜索区间缩小一半。

以 [1, 2, 2, 3, 4, 5, 6, 7] 为例，一共有 8 个数，每个数都在 1 和 7 之间。1 和 7 的中位数是 4，遍历整个数组，统计小于 4 的整数的个数，至多应该为 3 个，如果超过 3 个就说明重复的数存在于区间 [1,4) （注意：左闭右开）中；否则，重复的数存在于区间 [4,7]（注意：左右都是闭）中。这里小于 4 的整数有 4 个（它们是 1, 2, 2, 3），因此砍掉右半区间，连中位数也砍掉。以此类推，最后区间越来越小，直到变成 1 个整数，这个整数就是我们要找的重复的数。

代码实现：

class Solution {

    public static int findDuplicate(int[] nums) {

        int len = nums.length;

        int left = 1;

        int right = len - 1;

        while (left < right) {

            int mid = (left + right) / 2;

            int count = 0;

            for (int i = 0; i < len; i++) {

                if (nums[i] <=mid) {

                    count++;

                }

            }

            if (count > mid) {

                right = mid;

            } else {

                left = mid + 1;

            }

        }

        return left;

    }

}

时间复杂度：O(nlogn)

空间复杂度：O(1)

巴特西

Leetcode题目287.寻找重复数（中等）

最新文章

热门文章