leetcode 287. Find the Duplicate Number (floyd判圈算法找重复元素)
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.
Note:
1. You **must not** modify the array (assume the array is read only).
2. You must use only constant, _O_(1) extra space.
3. Your runtime complexity should be less than `O(n2)`.
4. There is only one duplicate number in the array, but it could be repeated more than once.
思路：O(n^2)的复杂度暴力即可，说个O(n)复杂度的解法。
需要注意元素范围1..n是个很重要的条件。
使得我们可以把位置和元素映射起来。
可以看成一个迭代函数
由于存在重复重复元素，因此一定存在一个环。
因此可以用floyd判圈算法。
这算法以前遇到过sgu455 解题报告，所以不算很陌生...
但是从有重复元素没有联想到会有环orz，我好菜啊...
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月05日 星期三 15时16分11秒
4File Name :287.cpp
5************************************************ */
6/* ***********************************************
7Author :111qqz
8Created Time :2017年04月05日 星期三 14时58分11秒
9File Name :287.cpp
10************************************************ */
11class Solution {
public:
1 int findDuplicate(vector<int>& nums) {
2 int slow = nums[0];
3 int fast = nums[nums[0]];
4 while (slow!=fast)
5 {
6 slow = nums[slow];
7 fast = nums[nums[fast]];
1 printf("slow:%d fast:%d\n",slow,fast);
2 }
3 fast = 0 ;
4 while (fast != slow)
5 {
6 fast = nums[fast];
7 slow = nums[slow];
8 }
9 return slow;
}
};