面试题：在指定范围整数数组中查找重复元素的最优解法问询

刚好之前琢磨过这个面试题，这个基于数值范围二分的解法确实能满足O(nlogn)时间复杂度+O(1)空间复杂度的要求，我来一步步理清楚思路：

问题回顾 #

给定一个包含n+1个整数的数组，所有整数取值范围为[1,n]，数组存在k个（k≥1）重复元素，且每个重复元素可出现两次以上。要求以最优时间和空间复杂度找出其中一个重复元素。

解法思路：二分查找+鸽巢原理 #

核心是不对数组本身做排序或修改，而是针对元素的取值范围做二分，利用鸽巢原理判断重复元素所在的区间，全程只需要几个变量统计计数，所以空间是O(1)。

具体步骤：

• 先设定数值范围的左右边界：left = 1，right = n（因为所有元素都在[1,n]里）
• 开始二分循环：
  1. 计算中间值 mid = (left + right) // 2
  2. 遍历整个数组，统计其中小于等于mid的元素总个数，记为count
  3. 用鸽巢原理判断：
     • 如果count > mid：说明[1, mid]这个区间里的元素数量，比区间内的不同数值总数还多，那这个区间里肯定藏着重复元素，把右边界right改成mid
     • 如果count <= mid：说明[1, mid]里的元素都是唯一的（每个数恰好出现一次），重复元素一定在[mid+1, right]里，把左边界left改成mid + 1
• 当left == right时，这个值就是我们要找的其中一个重复元素

举个例子更直观 #

比如数组是[1,3,4,2,2]，n=4：

1. 第一次mid=(1+4)//2=2，统计≤2的元素：1、2、2，共3个。3>2，所以重复元素在[1,2]，right=2
2. 第二次mid=(1+2)//2=1，统计≤1的元素：只有1，共1个。1=1，所以重复元素在[2,2]，left=2
3. 此时left=right=2，直接得到结果

这个方法的好处是完全不依赖额外空间，也不用改原数组，时间上每次二分要遍历一次数组，总共logn轮，所以总时间是O(nlogn)，在不能修改数组、又要低空间的场景下，这是非常合适的最优解之一。

内容的提问来源于stack exchange，提问作者Rose M