Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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 {
12
13public:
14
15 int findDuplicate(vector<int>& nums) {
16 int slow = nums[0];
17 int fast = nums[nums[0]];
18 while (slow!=fast)
19 {
20 slow = nums[slow];
21 fast = nums[nums[fast]];
22
23 printf("slow:%d fast:%d\n",slow,fast);
24 }
25 fast = 0 ;
26 while (fast != slow)
27 {
28 fast = nums[fast];
29 slow = nums[slow];
30 }
31 return slow;
32
33 }
34
35};