題目描述:
給定一個字串 s,刪除最少的字元使得每個字元的出現頻率都是唯一的(不存在兩個不同字元有相同頻率)。頻率為 0 的字元不計入。
解題思路:
核心想法:高頻率的字元盡量保持不變,衝突時往下調整。由大到小處理可以確保每次調整幅度最小。
時間複雜度:O(n + 26 log 26) = O(n) — 統計頻率 O(n),排序固定 26 個元素為常數時間。
空間複雜度:O(1) — 頻率陣列大小固定為 26。
1. Count frequency of each character in s
2. Sort the 26 frequencies in descending order
3. Set deletions = 0
4. For i from 1 to 25:
a. If freq[i] == 0, break
b. If freq[i] >= freq[i-1]:
- target = max(0, freq[i-1] - 1)
- deletions += freq[i] - target
- freq[i] = target
5. Return deletions使用 HashSet O(n):統計頻率後,用 HashSet 記錄已使用的頻率值。對每個非零頻率,若已存在於 Set 中則逐步減 1 直到找到未使用的值或降至 0。最壞情況內層 while 累計 O(n) 次。
計數排序 O(n):由於頻率最大為 n,可以用計數排序替代比較排序。對頻率的頻率再做處理,從高到低分配。較複雜但嚴格 O(n)。