題目敘述
題目會給我們一個輸入整數陣列arr，和一個初始化的刪除次數k？
我們可以任意選擇從arr中刪除k個陣列元素，請問最後留下來的數字，最少會有幾個不同的數字?
註: 最後不同的數字越少越好。測試範例
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
刪除一個4
最後只留下5
len( set(5) ) = 1
Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
刪除一個4
刪除一個2
再任選刪除一個1 或者 一個3
最後者剩下1, 3
len( set(1,3) ) = 2
約束條件
Constraints:
1 <= arr.length <= 10^5
arr陣列長度介於1~十萬之間。
1 <= arr[i] <= 10^9
陣列元素都介於1~十億之間。
0 <= k <= arr.length
k值介於0~arr陣列長度 之間。
演算法 Hash table + 出現次數的直方圖 + Greedy
怎麼刪除，才能讓最後不同的數字最少?
有一個基本直覺得想法，先刪除那些烙單或者出現比較少的數字?
為什麼?
因為k值是有限的，必須在k次內盡可能刪掉和別人不一樣的數字。
因此，到這邊有了一個Greedy演算法的想法:
先根據輸入陣列建立每個陣列元素的出現次數統計。
再建立一個關於出現次數的直方圖，每一回合刪除時，都從出現次數最少的開始刪，
一值到刪除次數用完為止。
程式碼 Hash table + 出現次數的直方圖 + Greedy
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
## Dictionary
# key: unique array number
# value: corresponding occurrence
occurrence = Counter(arr)
# n = Counting of unique number in input array
n = len(occurrence)
## Dictionary
# key: occurrence
# value: distribution of occurrence
histogram = Counter( occurrence.values() )
## Greedy stategy
# Remove unique number as many as possible
# Remove number from low occurrence to high occurrence
for occ in range(1, len(arr)+1 ):
if k >= occ * histogram[occ]:
# We can remove all number with current occurrence
# Update available removing count
k -= occ * histogram[occ]
# Update remaining count of unique numbers
n -= histogram[occ]
else:
# We can only remove part of number with current occurrence
# k = 0 after this round
# Update remaining count of unique numbers
return n - k // occ
return n
複雜度分析 Hash table + 出現次數的直方圖 + Greedy
時間複雜度:
建立字典，和迴圈迭代都是一次線性掃描，皆為O(n)
空間複雜度:
字典長度最大為O(n)，最差情況發生再每個數字都不一樣的時候。
關鍵知識點
怎麼刪除，才能讓最後不同的數字最少?
有一個基本直覺得想法，先刪除那些烙單或者出現比較少的數字?
為什麼?
因為k值是有限的，必須在k次內盡可能刪掉和別人不一樣的數字。
Reference:
[1] Least Number of Unique Integers after K Removals - LeetCode
