LeetCode 筆記｜217. Contains Duplicate

發表於 更新於

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

(給定一整數陣列，判斷其中是否含重複的數字。)

Example:

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

解題思路

若 array 含重複數字，則有以下特性：

  • 數字重複出現
  • array 長度大於其中數字種類數
  • 若將 array 排序，則重複的數字比鄰出現

根據第一種特性，可用 hash table 存儲讀過的數字，再判斷讀入的數字是否已存在 hash table 中。此處，我以 python 的 dict 充作 hash table 來實踐這個想法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        occur = {}
        for n in nums:
            if n in occur.keys():
                return(True)
            else:
                occur[n] = n
        return(False)
```    

由於計算時間和空間需求都隨陣列大小線性增長，所以時間與空間複雜度都是 $O(n)$

除了 `dict`，python 的 `set` 也能體現 hash table 的特性。`set` 可想像為僅有 key 的 `dict`，由於 `set` 的元素皆獨一無二，故可將 array 轉為 `set`，再比較兩者的長度。若 `set` 長度小於 array，則表示 array 含重複值。
```python
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(set(nums)) != len(nums):
            return(True)
        else:
            return(False)

至於先排序，再比較數值兩側是否有重複值的做法，可參考：LeetCode 刷題紀錄 ｜217. Contains Duplicate (Easy)

延伸討論