Problem#
給你一個整數陣列 arr 和一個整數 k ，問你在移除 k 個元素後剩下最少幾種不同的數字？
測資限制#
- $1 \le n \le 10^5$
- $1 \le val \le 10^9$
- $0 \le k \le n$
想法#
因為要刪除元素後，種類數要最小，所以要盡量的減少種類數，也就是在刪除 k 個元素時先刪出現次數較少的，這樣比較快消滅該數字種類，達到最小。
可以用 priority queue 來維護當前最小出現次數，每次從中 pop 最小的，減去一，如果小於等於 0 的話就代表該數字已被消滅；反之，push 回去。直到刪去 k 個數字，priority queue 的 size() 即為答案。
AC Code#
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(n)$