即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【LeetCode】287.Find the Duplicate Number解题报告

编程语言 haoxiaoxiaoyu 27℃ 0评论

【LeetCode】287.Find the Duplicate Number解题报告

tags: Array

题目地址:https://leetcode.com/problems/find-the-duplicate-number/#/description

题目描述:

  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.

题意:1到n的范围内,包含n+1个整数,其中有重复的只有一个,注意重复次数可能不只一次。

Solutions:

解法一:

  既然重复次数可能不只一次,所以就不能用求和再相减了,所以说换一种方法,自己想到利用set,但是效果不好,只超了百分之10的提交。

public class Solution {
    public int findDuplicate(int[] nums) {
        Set set= new HashSet();
        int result=0;
        for(int i=0;iif(!set.add(nums[i])){
                result=nums[i];
                break;
            }else{
                set.add(nums[i]);
            }
        }
        return result;
    }
}

解法二:

  后面看到一种解法,超过大约百分之97。举例,

index: 0 1 2 3 4 5

value: 1 4 0 0 3 2


这里写图片描述

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int slow = n;
        int fast = n;
        do{
            slow = nums[slow-1];
            fast = nums[nums[fast-1]-1];
        }while(slow != fast);
        slow = n;
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[fast-1];
        }
        return slow;
    }
}

Date:2017年6月7日

转载请注明:CodingBlog » 【LeetCode】287.Find the Duplicate Number解题报告

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情