LeetCode题目链接:287. Find the Duplicate Number

2017/04/01 Algorithm

tips: 链表是够有环算法应用

LeetCode题目链接:287. 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.</br> Note:</br> 1. You must not modify the array (assume the array is read only).</br> 2. You must use only constant, O(1) extra space.</br> 3. Your runtime complexity should be less than O(n2).</br> 4. There is only one duplicate number in the array, but it could be repeated more than once.</br>

分析:

根据鸽笼原理,显然至少有一个数字是重复的,然后我们来解决怎么找到这个重复的数字。在这个数组中,我们将数组的下标和值进行映射,因为存在重复的数字,则必然存在两个下标对应同一个数字。举例如下:

3,1,3,4,2
0,1,2,3,4 我们从0开始找,则0-3-4-2-3-4-......,序列从第二次访问3开始,进入了无限循环,我们将序列看成一个链表,就转化成了有环链表的问题。因为环的存在,我们用两个指针分别以每次1个节点和每次2个节点的速度遍历,则两个指针必然会相遇,此时快指针比满指针多走了n个环的距离。现在我们来分析怎么找到环的起点,也就是本题中重复出现的数字。设从链表起点到环的起点的距离为l,环的起点到相遇点距离为x,环的周长为r,则快速指针走了

s1 = l + x + n * r 的长度。慢速指针走了

s2 = l + x 快速指针是慢速指针速度两倍,则

s1 = 2 * s2 易得:

n * r = l + x 即

(n - 1) * r  + r - x = l 我们让快速指针以1个节点每次的速度从链表起点开始走l步,慢速指针从相遇点走l步,即慢速指针走了(n - 1) * r  + r - x步,相遇点距离换的起点x步,则最终慢速指针距离相遇点(n - 1) * r  + r - x + x = n * r步,即慢速指针也停在环的起点处。换句话说,此时的相遇点就是环的起点。

源代码

public class Solution {
    public int findDuplicate(int[] nums) {
    	int fast = 0; //快速指针
    	int slow = 0; //慢速指针
    	
    	fast = nums[nums[fast]]; //每次走两步
    	slow = nums[slow];  //每次走一步
    	
    	while(fast != slow){    //直到两指针相遇
    		fast = nums[nums[fast]];
    		slow = nums[slow];
    	}
    	
    	fast = 0; //快速指针从头开始每次走一步
    	while(fast != slow){  //第二次相遇点就是环的起点
    		fast = nums[fast];
    		slow = nums[slow];
    	}
    	
    	return fast;
        
    }
}

Search

    Table of Contents