跳到主要内容

LeetCode 287. 寻找重复数

本节目标

在数值范围中二分，利用计数与抽屉原理定位不修改数组的重复值。

这道题是分治与二分综合框架中的拓展题。数组长度为 n + 1，但每个值都落在 1..n；即使不排序、不修改数组，也能在数值范围里定位重复值。

查看原题

题意与约束​

给定长度为 n + 1 的整数数组 nums，每个整数在 1 到 n 之间，恰有一个值重复出现一次或多次。返回该重复值，且不能修改输入数组。

朴素思路与瓶颈​

两两比较可在不改数组时找出重复值，但需要 O(n²)；哈希集合可降到 O(n) 时间，却使用 O(n) 额外空间；排序或原地标记又会改变输入。快慢指针也能利用函数图结构求解，但本题选择值域二分，练习在 O(1) 额外空间下把抽屉原理变成计数判定。

在数值范围中二分​

候选重复值在 [1, n]，而不是数组下标区间。取 middle 后，遍历数组统计 count：值不大于 middle 的元素个数。

  • count > middle 时，重复值在 [left, middle]；
  • 否则重复值在 [middle + 1, right]。

每轮缩小值域，直到左右端点相同。源码只读取数组完成计数，因此不会改变调用方输入。

计数如何连接抽屉原理​

考虑数值盒子 1..middle，一共只有 middle 个不同的可选值。如果数组中有超过 middle 个元素落进这些盒子，依据抽屉原理，至少一个盒子装入了两个元素。题目保证只有一个重复值，所以它必在左半值域。

反过来，若 count <= middle，前 middle 个盒子没有被迫发生重复，唯一重复值只能在右半。这个判断不要求数组局部有序，单调来源是随着 middle 增大，累计计数只会增加。

代码实现​

C++ 与 Python 都维护闭区间 [left, right]，并在 count > middle 时保留左端，否则把左端移动到 middle + 1。实现中没有排序、交换或标记数组元素。

C++17
#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1;
        int right = static_cast<int>(nums.size()) - 1;

        while (left < right) {
            int middle = left + (right - left) / 2;
            int count = 0;
            for (int number : nums) {
                if (number <= middle) {
                    count++;
                }
            }
            if (count > middle) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }
};

复杂度分析​

  • 时间复杂度：O(n log n)。值域二分 O(log n) 次，每次完整计数 O(n)。
  • 空间复杂度：O(1)。只使用计数器和边界变量。

易错点​

  • 对数组下标二分，忽略重复值属于 1..n 的数值空间。
  • 将条件写为 count >= middle；恰好有 middle 个元素时并不能推出左侧存在重复。
  • 为了计数先排序或原地标记，违反不修改输入的约束。
  • 用快慢指针作为主解法，错过本题的值域计数模型。

模式迁移​

当对象可映射到有限整数值域且计数能暴露拥挤区间时，抽屉原理可以成为二分判定。若问题需要恢复重复位置、处理多个重复值或建立在线查询，则应转向哈希表、位图或其他数据结构；本题只需定位唯一重复的数值。