Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 287. Find the Duplicate Number

發表於 分類於 ， ， Disqus：
這題是一題把陣列當成類似 linked list 的題目，目標是找到陣列中重複的元素

前言

　　這題是一題把陣列當成類似 linked list 的題目，目標是找到陣列中重複的元素，因它只對陣列進行了兩次循環，而每次循環都是線性時間的運作，時間複雜度可達 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

給定一個整數陣列 nums 含有 n + 1 個整數，每個整數都在 [1, n] 範圍包含裡。
nums 中只有一個重複的數字，回傳這個重複的數字。
你必須在不能修改 nums 的情況下解決這個問題，而且只能使用常數的記憶體空間。

題目連結：https://leetcode.com/problems/find-the-duplicate-number/

題目限制

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n

All the integers in nums appear only once except for precisely one integer which appears two or more times.

範例

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

思路&筆記

暴力的解法是利用雙迴圈，找出相等的元素後就是答案，結果超過時間限制 (不採用)

另一種解法，運用 HashSet 方法的特性，找出不能出現的元素

  • 循環 nums 陣列，把每個元素添加到 HashSet 中
  • 如果發現某個元素已經存在於 HashSet 中，那麼這個元素就是重複的
  • 回傳這個元素

第三種解法是使用鏈表的特性，在鏈表內的元素不會有重複，有重複的話會形成一個環

  • 把當前的元素，當成下一個元素的 index，變成一個類似 linked list 的鏈表
  • 然後設定一組快慢指針，慢指針走一步，快指針走兩步，在鏈表中有重複的元素，快指針會先走到有重複元素的環內，慢指針也會走到有重複元素的環內，這時如果快慢指針都走到相同的元素，代表這個元素就是我們要找的重複的元素
  • 例如走過 2 這個元素，後面又再次遇到 2 的時候，代表 2 是重複的元素，然而會形成一個環，在這個有重複元素的還內一直打轉
  • 另外設定第三個指針檢查，用意是找出環的頭，無論用慢指針或快指針去和檢查指針比對都行，快慢指針是一樣的元素

while 迴圈從 0 開始走，到 3 的時候已經遇到一個 2 了，繼續走到 4 的時候又遇到一個 2

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 暴力的解法是利用雙迴圈，找出相等的元素後就是答案，結果超過時間限制 (不採用)
class Solution {
    public int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]){
                    return nums[i];
                };
            };
        };
        return -1;
    };
};

// 另一種解法，運用 HashSet 方法的特性，找出不能出現的元素
class Solution {
    public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>(); // 集合
        for(int num : nums) {
            // 添加進去時會判斷有沒有 (重複元素不會被添加)
            if(!set.add(num)) {
                return num; // 回傳當下這個元素
            }
        }
        return -1;
    }
}

// 第三種解法是使用鏈表的特性，在鏈表內的元素不會有重複，有重複的話會形成一個環
class Solution {
    public int findDuplicate(int[] nums) {

        int slow = 0; // 慢指針
        int fast = 0; // 快指針
        int check = 0; // 確認指針
            
        while( true ){
            slow = nums[slow]; // 取得 index 位置(走一步)
            fast = nums[nums[fast]]; // 取得 index 位置後，從位置再取一次新的位置 (等於走兩步)
            
            // 如果快慢指針一樣
            if( slow == fast ){
                break;
            }
        }
        
        // 找出循環的頭
        while( true ){
            slow = nums[slow];
            check = nums[check]; // 檢查指針
            
            // 如果慢指針和檢查指針一樣
            if( slow == check ){
                break;
            }
        }

        return check;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        
        slow = 0
        fast = 0
        check = 0
        
        while True:
            slow = nums[slow] # 取得 index 位置(走一步)
            fast = nums[nums[fast]] # 取得 index 位置後，從位置再取一次新的位置 (等於走兩步)
            
            # 如果快慢指針一樣
            if slow == fast:
                break

        # 找出循環的頭
        while True:
            slow = nums[slow]
            check = nums[check]
            
            # 如果慢指針和檢查指針一樣
            if slow == check:
                break
        
        return check

成績

Language Runtime Memory
Java 4ms 59.49MB
Python 520ms 30.95MB