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

思路: 题目不让修改array,禁止排序。 要求O(1)的额外空间,那么也就不能用hashmap来记录元素。给定的数组长度为1+n, 而每个数字的范围又是1-n之间,由于给定数组的特殊性。 我们可以想到用用linkedlist 找环的起始位置来解这道题目。

  1. 快慢指针找环:
public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) return 0;
        int fast = nums[nums[0]];
        int slow = nums[0];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
  1. 二分法
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s