您的位置 首页 JAVA(2017)

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.

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.

思路:

要理解这道题,先要理解题目142:https://blog.jing.do/5371

把这个array看成linkedlist,快慢两个指针,如果没有重复的,他们永远碰不到,如果有重复,fast的指针会卡在那边,等待slow的指针,从而碰面。

碰到之后,从初始(最后或者最前)开始遍历,让两者交汇,交汇的值就是重复的。

如果很难理解,先理解142。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[nums.length-1];
        int fast = nums[nums[nums.length-1]-1];
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[nums[fast-1]-1];
        }
        slow = nums.length;
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[fast-1];
        }
        return slow;
    }
}
看完了?留个评分呗?
[0人评了分,平均: 0/5]

本站原创文章皆遵循“署名-非商业性使用-相同方式共享 3.0 (CC BY-NC-SA 3.0)”。转载请保留以下标注:

原文来源:《287. Find the Duplicate Number》

发表评论

邮箱地址不会被公开。

返回顶部