題目描述:給定整數陣列 arr,判斷陣列中每個值的出現次數是否都各不相同(即所有出現次數構成的集合中沒有重複值)。
解題思路:兩步驟雜湊法。第一步:用雜湊表(unordered_map)統計每個值的出現次數。第二步:將所有出現次數放入集合(unordered_set),若集合大小等於雜湊表大小,代表沒有重複次數,回傳 true;否則回傳 false。核心觀察:若次數有重複,集合大小會比 map 小。整個過程只需兩次線性掃描。
時間複雜度: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) 且有較好的快取效能。