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.

Example 1:

1
2
Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: [3,1,3,4,2]
Output: 3

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. Linked List Cycle II 的思路基本一致。这道题可以把数组当做一个图，对于数组中的值，i -> A[i] 是一条有向连接，由于数组的长度是 n+1, 而值的范围为 1~n，重复的那个值就相当于有两个节点指向它，因此这个图中一定存在环。求这个环的入口，逻辑就跟 142. Linked List Cycle II 这道题没什么区别了。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums.length < 1) {
            return -1;
        }
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        slow = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
}

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    slow, fast = nums[slow], nums[nums[fast]]
    
    for slow != fast {
        slow, fast = nums[slow], nums[nums[fast]]
    }
    slow = 0
    for slow != fast {
        slow, fast = nums[slow], nums[fast]
    }
    return fast
}

相关问题

题目来源