【LeetCode】Contains Duplicate – 抓出多餘的人 – 陣列、雜湊 Hash、排序

tags: leetcode

https://leetcode.com/problems/contains-duplicate/description/

題目 LeetCode 217

思路

1. 這題很簡單，小學生都會，有很多做法可以解決這題，就像 two sum 一樣
2. 重點是背後的分析：時間複雜度、空間複雜度、程式語言的語法。我們一個個來看
3. 一定要先釐清題目，這題給的 nums 是有排序的嗎? 從 Example 1 看起來是沒有
4. 不然先暴力解吧，要看看有沒有重複的數字，我們就來兩兩比較，跟 two sum 一樣，如果不熟悉 two sum 可以看前面的文章
5. 兩兩比較我們可以得到暴力解 – [解法一] ，暴力解總共要比幾次呢？ 總共 $N(N-1) / 2$ 次，所以時間複雜度是 $O(N^2)$，我們沒有使用額外的記憶體，所以是 $O(1)$
6. 結果就 Exceed Time Limit 了QQ
7. 既然要看數字有沒有重複，我們只要 記得 我們看過的數字就好啦，這時候可以使用一個 集合 set 來記下我們看過的數字，我們可以得到 [解法二]
8. 把元素放到集合裡只需要花 $O(1)$ 的時間，看一個元素是否在集合裡也是 $O(1)$ 的時間，所以這題的時間複雜度是 $O(N)$；我們用了額外的記憶體來紀錄下我們看過的元素，所以空間複雜度也是 $O(N)$

解法一

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # Brute Force - Time Limit Exceeded
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

解法二

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # Hashing
        memory = set()
        for n in nums:
            if n in memory:
                return True
            else:
                memory.add(n)
        return False

解法三

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        Solution 2: Sorting
        nums = sorted(nums)
        for i in range(len(nums) -1):
            if nums[i] == nums[i+1]:
                return True
        return False

筆記

• 兩兩握手的問題阿嬤小學就學過了，所以這題真的是小學生就會的
• 除了上述的解法一和解法二，我們也可以透過排序並且檢查是否存在同樣數字相鄰的情況，這樣子的時間複雜度會是 $O(N~log~N)$，大家可以試試看，我放在 [解法三]
• 這題真的不難，重點是各種不同解法的時間複雜度分析，暴力解、排序、Hashing這些操作的複雜度都是要刻在腦子裡的
• HackMD 筆記 https://hackmd.io/@ga642381/ry5TsNJqi