How do I approach the 'Find the Duplicate Number' problem using binary search?

Use binary search on the range from 1 to n. Count the numbers less than or equal to the middle value to adjust your search space towards the half that contains the duplicate.

What are the main constraints in the 'Find the Duplicate Number' problem?

The solution must be found using constant extra space and without modifying the array. The time complexity should be efficient enough to handle large arrays.

How can I avoid using extra space in this problem?

The key to avoiding extra space is using a binary search combined with two pointers to find the duplicate number in-place, without additional data structures.

What is the time complexity of the solution for the 'Find the Duplicate Number' problem?

The time complexity is O(n log n), where n is the length of the array, due to the binary search process combined with the cycle detection technique.

How does the two pointers technique work in this problem?

The two pointers technique detects a cycle in the array, which leads to identifying the duplicate number. One pointer moves slowly, while the other moves quickly to find the meeting point.

#287

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n ），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。示例 1：输…

数组双指针二分查找位运算

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

lightbulb

解题思路

方法一：二分查找

我们可以发现，如果 $[1,..x]$ 中的数字个数大于 $x$ ，那么重复的数字一定在 $[1,..x]$ 中，否则重复的数字一定在 $[x+1,..n]$ 中。

因此，我们可以二分枚举 $x$ ，每次判断 $[1,..x]$ 中的数字个数是否大于 $x$ ，从而确定重复的数字在哪个区间中，进而缩小区间范围，直到找到重复的数字。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        def f(x: int) -> bool:
            return sum(v <= x for v in nums) > x

        return bisect_left(range(len(nums)), True, key=f)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to recognize binary search as the key approach to narrowing down the duplicate.
question_mark
Test the candidate's understanding of constant space solutions and their ability to adapt algorithms to fit stringent space constraints.
question_mark
Assess the candidate's knowledge of the two pointers technique and how they apply it to detect cycles in arrays.

warning

常见陷阱

外企场景

error
Not adhering to the constant space requirement by using extra data structures like hashmaps or sets.
error
Failing to recognize the binary search approach as the optimal solution, opting for brute force methods instead.
error
Misunderstanding the two pointers technique, leading to incorrect cycle detection or failure to identify the duplicate number.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Apply the same technique to find the duplicate in a linked list instead of an array.
arrow_right_alt
Modify the problem to allow more than one duplicate number and adapt the algorithm.
arrow_right_alt
Change the problem to include multiple cycles and test the candidate's ability to handle more complex scenarios.

help

常见问题

外企场景

继续练习

#268 丢失的数字 #349 两个数组的交集 #350 两个数组的交集 II