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:
O(n2).以下为时间复杂度O(n)的算法。
class Solution { public: int findDuplicate(vector<int>& nums) { int n = nums.size(); int i; int k=1; int step = 1; int fast = n-1; int slow = n-1; while(true) { slow = nums[slow] -1; fast = nums[nums[fast]-1] -1; if(fast == slow) { break; } } fast = n-1; while(true) { slow = nums[slow] -1; fast = nums[fast] -1; if(fast == slow) return slow+1; } return 0; } };
LeetCode 287 Find the Duplicate Number
原文：http://www.cnblogs.com/julyfrost/p/5445721.html