付費限定文章

字典應用題_判斷是否每個元素的出現次數都不同 Leetcode #1207 精選75

Susan Holt Simpson on Unsplash

題目敘述

題目會給定一個整數陣列arr，要求我們判斷是否每個元素的出現次數都不同?

題目的原文敘述

測試範例

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

約束條件

Constraints:

• 1 <= arr.length <= 1000

陣列arr的長度介於1 ~ 1000之間

• -1000 <= arr[i] <= 1000

每個陣列元素都介於-1000 ~ 1000之間。

演算法

看到統計出現次數，就聯想到雜湊映射表Hash map，在python裡面就是字典dictionary。其中，遇到可迭代的對象，還有自動針對每個元素計數的Counter。

因此，我們只要統計每個元素的出現次數。

接下來，判斷出現次數的集合長度，是否等於出現次數陣列的長度。

假如是，代表每個元素的出現次數都不同，返回True；若不是，則返回False。

程式碼

from collections import Counter
from typing import List

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        
					# dictionary:
					# key: number
					# value: occurrence of number
        num_occ_dict = Counter( arr )
        
					# occurrences of each number
        occ = num_occ_dict.values()
        
					# if all occurrences are unique, then the length will be equal between occ and set(occ)
        return len(occ) == len( set(occ) )

關鍵知識點