Question
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.
Code
public class Solution {
public int findDuplicate(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int fast = 0, slow = 0;
do {
fast = nums[nums[fast]];
slow = nums[slow];
} while (fast != slow);
int result = 0;
while (result != slow) {
result = nums[result];
slow = nums[slow];
}
return slow;
}
}
Solution
假設(shè)數(shù)組中沒有重復(fù)，那我們可以做到這么一點(diǎn)氛堕，就是將數(shù)組的下標(biāo)和1到n每一個(gè)數(shù)一對一的映射起來紊搪。比如數(shù)組是213,則映射關(guān)系為0->2, 1->1, 2->3挤悉。假設(shè)這個(gè)一對一映射關(guān)系是一個(gè)函數(shù)f(n)桶唐，其中n是下標(biāo)缰儿，f(n)是映射到的數(shù)元镀。如果我們從下標(biāo)為0出發(fā)，根據(jù)這個(gè)函數(shù)計(jì)算出一個(gè)值掌测，以這個(gè)值為新的下標(biāo)内贮，再用這個(gè)函數(shù)計(jì)算，以此類推赏半，直到下標(biāo)超界贺归。實(shí)際上可以產(chǎn)生一個(gè)類似鏈表一樣的序列。比如在這個(gè)例子中有兩個(gè)下標(biāo)的序列断箫，0->2->3拂酣。
但如果有重復(fù)的話，這中間就會(huì)產(chǎn)生多對一的映射仲义，比如數(shù)組2131,則映射關(guān)系為0->2, {1婶熬，3}->1, 2->3。這樣埃撵，我們推演的序列就一定會(huì)有環(huán)路了赵颅，這里下標(biāo)的序列是0->2->3->1->1->1->1->...，而環(huán)的起點(diǎn)就是重復(fù)的數(shù)暂刘。
所以該題實(shí)際上就是找環(huán)路起點(diǎn)的題饺谬，和Linked List Cycle II一樣。我們先用快慢兩個(gè)下標(biāo)都從0開始谣拣，快下標(biāo)每輪映射兩次募寨，慢下標(biāo)每輪映射一次，直到兩個(gè)下標(biāo)再次相同森缠。這時(shí)候保持慢下標(biāo)位置不變拔鹰，再用一個(gè)新的下標(biāo)從0開始，這兩個(gè)下標(biāo)都繼續(xù)每輪映射一次贵涵，當(dāng)這兩個(gè)下標(biāo)相遇時(shí)列肢，就是環(huán)的起點(diǎn)，也就是重復(fù)的數(shù)宾茂。
