总结 Leetcode find-the-duplicate-number 的做法。

Problem

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($n^2$).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution

Solution 1: Floyd’s_Tortoise_and_Hare

根据抽屉原理1 , $ n+1 $ 个数分布在 $ 1 $~ $ n $ 之间, 至少有一个数重复出现两次。

举个例字:将数组nums=[3,1,3,4,2]

index 0 1 2 3 4
number 3 1 3 4 2

抽象为链表: $ 0 ->3->4->2->3 $ , 所以在 3 处开始循环。

利用 Floyd’s Tortoise and Hare 算法:

利用两个指针(快(hare)慢(tortoise)指针),快指针的移动速度是慢指针移动速度的两倍,链表如果有环,指针必会在环内某一元素处交汇。由相遇元素开始寻找环的第一个元素,使慢指针回到起点,快指针继续呆在交汇点。接下来两者以相同的速率开始移动,下一次两者交汇处,即循环的起点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int findDuplicate(int[] nums) {
            int tortoise = nums[0];
            int hare = nums[nums[0]];
      //Find the intersection.
            while (tortoise != hare) {
                tortoise = nums[tortoise];
                hare = nums[nums[hare]];
            }
      //find the first element of circle.
            tortoise = 0;
            while (tortoise != hare) {
                hare = nums[hare];
                tortoise = nums[tortoise];
            }
            return hare;
        }
}

证明:

pic1

tortoise 与 hare相遇 $x _i== x_{2i} $ ,

$\lambda $ 表示循环的长度。

此时:

$$ i=x+y+p\lambda $$

$$2i=x+y+q\lambda$$

$$ 2x+2y+2p\lambda=x+y+q\lambda $$

$$ x+y=(q-2p)\lambda $$

找到交汇点(循环中的任一点)后,如何找循环开始的第一个点呢?

假设 tortorise 和 hare 相遇后,将 tortoise 置 0,回到起点,hare 原地不动,两者每次均移动一个单位,下次相遇点即为循环开始的点,假设 tortoise 移动 $ x $ 单位后到达循环起点,由 $$ x+y=(q-2p)\lambda $$ 知:hare 移动 $ x+y $ 个单位将回到原位置,如图所示,如果少移动 $ y $ 个单位即恰好到循环起点,得证。

练习一下?

Leetcode_linked-list-cycle-ii

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int findDuplicate(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;// avoid overflow
            int cnt = 0;
            for (int i : nums) {
                if (i <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

此外还有两种解法但不满足题目要求,但可以通过评测。

Solution 3: Sorting

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public int findDuplicate(int[] nums) {
 			  Arrays.sort(nums);
              for(int i=1;i<nums.length;i++){
                  if(nums[i-1]==nums[i]){
                      return nums[i-1];
                }
            }
           return -1;
        }
}

修改了数组,不符合要求一。

Solution 4: HashSet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {   
public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i]))
                return nums[i];
            set.add(nums[i]);
        }
        return -1;
    }
}

空间复杂度为 $O(n)$ , 时间复杂度$O(n).$

Reference