解題說明
Unique Number of Occurrences
題目描述:給定整數陣列 arr,判斷陣列中每個值的出現次數是否都各不相同(即所有出現次數構成的集合中沒有重複值)。
解題思路:兩步驟雜湊法。第一步:用雜湊表(unordered_map)統計每個值的出現次數。第二步:將所有出現次數放入集合(unordered_set),若集合大小等於雜湊表大小,代表沒有重複次數,回傳 true;否則回傳 false。核心觀察:若次數有重複,集合大小會比 map 小。整個過程只需兩次線性掃描。
C++ 解法
複雜度分析
時間複雜度:O(n) — 兩次線性掃描,分別統計頻率和插入集合。
空間複雜度:O(k) — k 為陣列中不同值的數量,儲存頻率雜湊表和次數集合。
虛擬碼
1. Initialize empty frequency map 2. For each element x in arr: count[x]++ 3. Insert all frequency values into a set 4. Return set.size() == map.size()
其他解法
排序法:對陣列排序後用線性掃描統計每段連續相同元素的數量,再排序這些數量,檢查是否有相鄰相等值。時間複雜度 O(n log n),不如雜湊表方法。
位元集合:由於陣列長度 ≤ 1000,出現次數最大為 1000,可用大小 1001 的 bool 陣列(bitset)代替 set,空間固定 O(1) 且有較好的快取效能。
延伸思考
- 若需要同時找出哪些值的出現次數重複,如何修改解法?
- 如果陣列元素範圍很小(如 1~100),能否設計 O(1) 額外空間的解法?
- 此題能否在不使用任何額外資料結構的情況下原地解決?