题目

原题链接
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

给定一个包含$n+1$个元素的数组，每个元素都在$1$到$n$之间（闭区间），证明至少一个元素重复，找出重复元素。

随想

这也是我遇到的一个面试题，当时想了很长时间，表现也不太好。
这个题和另外一个题：每个元素出现两次，有一个出现一次（Leetcode 136 Single Number）较为类似，有正好反过来的感觉。Leetcode136那道题异或位运算直接秒之。
证明一定有一个重复元素并不难，根据抽屉原理即可。
下面说如何找到它。
注意：并不要求$1$到$n$中的元素都要出现，也即$[2, 2, 2]$这种输入也是合法的。

思路及代码

方法1 哈希表

用一个hash table去存储，然后查重复的元素。
平均时间复杂度是$\mathcal{O}(n)$，空间复杂度是$\mathcal{O}(n)$。

优点：

• 打破元素必须在$1$到$n$的约束，适用范围广
• 不修改输入参数
• 时间复杂度低

缺点：

• 空间复杂度高。

如果要求了空间复杂度是$\mathcal{O}(1)$，那么该如何做呢？

方法2 排序

对原数组排序，排序后找相邻重复元素。
平均时间复杂度是$\mathcal{O}(n\log n)$，空间复杂度是$\mathcal{O}(1)$。

优点：

• 打破元素必须在$1$到$n$的约束，适用范围广
• 空间复杂度低

缺点：

• 时间复杂度高
• 修改了输入参数

方法3 二分查找

对原数组进行二分查找，假如结果确定在在区间范围$[1,n]$中，则记$mid = \left \lfloor \frac{(1 + n)}{2} \right \rfloor$ ，统计$[1,mid]$的元素个数是否小于等于$mid -1 + 1$，如果是，说明结果在$[mid + 1, n]$，否则说明结果在$[1, mid]$；重复上述过程。
最坏时间复杂度$\mathcal{O}(n\log n)$，空间复杂度$\mathcal{O}(1)$。

优点：

• 空间复杂度低
• 不修改输入参数

缺点：

• 时间复杂度高

方法3可以看作是方法2的一个改进。
如果即要求空间复杂度空间复杂度$\mathcal{O}(1)$，又要求时间复杂度$\mathcal{O}(n)$，该如何实现呢？

代码

class Solution {
public:int findDuplicate(vector<int>& nums) {int left = 1, right = nums.size(), mid, count;while (left < right) {mid = (left + right) / 2;count = 0;for (int i = 0; i < nums.size(); ++i) {count += (nums[i] <= mid && nums[i] >= left);}if (count <= (mid - left + 1)) {left = mid + 1;} else {right = mid;}}return left;}
};

方法4 利用索引交换

把$1$到$n$都当作索引使用，例如把元素$a$放到数组$[a]$位置上。索引$[0]$是没有元素能放对的，所以可以一直用索引$[0]$中的元素交换它对应位置的元素，直到这两个元素相等，即找到了重复元素。
最坏时间复杂度$\mathcal{O}(n)$，空间复杂度$\mathcal{O}(1)$。因为每一次交换一定能放对一个元素，一共只有$n$个元素，所以最坏只需要交换$\mathcal{O}(n)$次。
（当时面试答得是这种方法，虽然后来手写代码写的是错的……emm）

优点：

• 空间复杂度低
• 时间复杂度低

缺点：

• 修改了输入参数

代码：

class Solution {
public:int findDuplicate(vector<int>& nums) {while (nums[0] != nums[nums[0]]) {swap(nums[0], nums[nums[0]]);}return nums[0];}
};

方法5 链表判环

这个是非常推荐的一种方法！
把索引当作是地址，0当作是链表头，那么本质上这个题就是在找环入口，而且是在一定有环的情况下。
这样的话用快慢指针即可。类似Leetcode 142 Linked List Cycle II，不会链表找入口的话可以先看下这个题.

最坏时间复杂度$\mathcal{O}(n)$，空间复杂度$\mathcal{O}(1)$。

优点：

• 空间复杂度低
• 时间复杂度低

缺点：

暂无

代码：

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;do {fast = nums[fast];fast = nums[fast];slow = nums[slow];} while  (fast != slow);  // 这个do-while的写法非常精巧，可以仔细品一品fast = 0;while (fast != slow) {fast = nums[fast];slow = nums[slow];}return fast;}
};