Problem
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.
1
2
3
4
5
6
7
8Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
Solution
Analysis
题目给定一个长度为n+1的数组, 数组中每个数字在[1,n]之间, 证明至少存在一个重复数字. 假设只有一个重复数字,找到这个数字.
如果只有这些背景的话,不可能被标为medium. 用hash表就可以解决. 但是题目还有额外要求:
- 数组只读,不能修改—-不能用数组中的数字做下标,移动数组: 这样移动后nums[i] = i+1, 当nums[i] == nums[j]说明重复, 返回这个数; 同时不能使用排序
- 常量空间—-不能使用hash表: O(n); 也不能创建新数组再排序
- 时间复杂度小于O(N*N)—不能用循环,暴力破解
- 只有一个数字重复,但可能重复多次(不仅一次).
在限制条件下, 我没有思路Sad…
看大佬的答案.使用二分查找. 二分查找要求数组是有序的, 而这里数组并不有序. 所以需要对二分查找做一个小变化, 我们对[1,n]这个有序区间进行二分, 对其中每个数num,计算小于等于num的数字的个数, 如果小于等于num,说明[1,num]不存在重复数字[1-num有这么多坑,现在正好填满, 而数组还有重复元素,说明在另外一个区间里],只可能在(num, n]之间, 反之.
还有另一种解法. 将这个数组看做链表. 用数组模拟链表, 如下图所示.
索引表示链表节点的值,元素值表示next指针. 由于这里存在重复元素, 也就是说这个链表存在环. 所以我们的问题就变成查找链表环的入口节点[这个入口节点就是重复节点].
比如例一:
1
2
3[1,3,4,2,2].
对应的链表为: 1->3->2->4->2. 重复节点是2.
类似查找链表的环入口节点, 可以参考剑指offer中链表中环的入口结点的解法.链表环的入口节点,我通常先使用一个快慢指针判断是否有环, 然后返回相遇节点, 然后再判断环的长度; 之后再用快慢指针,慢指针从头开始,快指针先走环的长度,然后当两个指针相遇时,就是环的入口节点.
还有另一种方法: 先用快慢指针,慢指针一次走一步,快指针走两步,判断是否有环; 然后慢指针重置为链表头,两个指针同时走,直到相遇,相遇节点就是重复节点,或者说入口节点[我是死记硬背的,原理不太清楚].
Code
Solution One
1 | class Solution { |
Solution Two
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findDuplicate(vector<int>& nums) {// 这里不用判断是否有环, 一定存在环. 因为肯定存在重复元素.
int slow = 0, fast = 0, t = 0;
while (true) {
slow = nums[slow];// 慢指针: 一次一步
fast = nums[nums[fast]];//快指针: 一次两步
if (slow == fast) break;// 找到环, slow是环内节点
}
while (true) {
slow = nums[slow];// 同时走
t = nums[t];// t初始为头结点
if (slow == t) break;// 相遇,found
}
return slow;
}
};
References
https://www.cnblogs.com/grandyang/p/4843654.html
http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
Conclusion
Binary Search: 要求一个区间有序. 一般情况下是数组区间有序, 这道题给我一个提示, 也可以是查找区间有序(要找的数的区间有序), 但数组并不有序,而是数组数的范围有序, 比如这里有序区间是[1,n]. 而且,刚开始我看到标签有binary search二分查找, 也想到了对[1,n]区间划分, 但之后我想的是对每个数组查找有多少个等于这个数字的个数, 并不是小于等于, 所以之后的区间再细分,无从下手了. 重点是: 有序区间, 区间细分, 根据mid的情况, 是左区间,还是右区间. 判断条件是什么? 想清楚这两个问题就可以使用二分查找, 要学会算法贯通, 找到算法的本质特性, 方便其通用性.