LeetCode -- Find the Duplicate Number

LeetCode -- Find the Duplicate Number

問題描述：


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:
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.


在一個數組中找到重復的那個。


由於題目限制了只能使用O(1)的空間，也不能修改參數數組。
因此不能排序，也不能創造一個標記數組來一次遍歷進行'填空'；並且，由於重復元素可以出現多次，也無法使用等差數列公式求和=>s，再用數組和-s的方式。
搜到了一種解法，比較巧妙，思路類似於那個題目：在一個鏈表中找到環，並找出那個環的位置。
1. 使用了快慢指針
2. 在快慢指針相遇的位置開始，慢指針與另一個從起始位置出發的指針每次走一步，直到它們相遇，就是那個重復節點發生的地方。


 



實現代碼：

public class Solution {
    public int FindDuplicate(int[] nums) 
    {
        // define slow and fast , fast each time move 2 times
        var slow = 0;
    	var fast = 0;
    	while(true)
    	{
    		slow = nums[slow];
    		fast = nums[nums[fast]];
    		if(slow == fast){
    			break;
    		}
    	}
    	
    	// now, lets create another pointer 'finder' from the start position. 
    	// slow will stay where it is.
    	// finder and slow each time move one step. next time this meet is where duplicate happens
    	var finder = 0;
    	while(true)
    	{
    		slow   = nums[slow];
    		finder = nums[finder];
    		if (slow == finder){
    			return slow;
    		}
    	}
    }
}