难度: Medium
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
示例 1：
输入：arr = [5,5,4], k = 1 输出：1 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：
输入：arr = [4,3,1,1,3,3,2], k = 3 输出：2 解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
提示：
1 <= arr.length <= 10^51 <= arr[i] <= 10^90 <= k <= arr.length运行时间: 317 ms
内存: 0.0 MB
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
freqDict = Counter(arr)
total = len(freqDict)
freqList = [freq for x, freq in freqDict.items()]
freqList.sort()
for freq in freqList:
if freq <= k:
k -= freq
total -= 1
return total
本题解的思路是首先使用一个哈希表（通过Counter实现）来统计数组中每个元素的频率。然后，将频率转换成列表并进行排序，以便从最少出现的元素开始移除，以尽可能减少数组中不同整数的个数。遍历排序后的频率列表，如果某个频率小于或等于剩余可移除的元素数k，就将该频率对应的元素完全移除，并相应地减少k的值和不同整数的计数。如果k为0或遍历完列表，则返回当前的不同整数个数。
时间复杂度: O(n + u log u)
空间复杂度: O(u)
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
freqDict = Counter(arr) # 使用Counter统计每个元素的频率
total = len(freqDict) # 不同整数的初始数量
freqList = [freq for x, freq in freqDict.items()] # 将频率转换为列表
freqList.sort() # 对频率进行排序
for freq in freqList: # 遍历排序后的频率列表
if freq <= k: # 如果当前频率小于等于剩余的k
k -= freq # 减少k
total -= 1 # 减少不同整数的数量
return total # 返回最终的不同整数的数量
在解决此问题时，使用哈希表来统计元素的频率是因为哈希表提供了高效的数据存储和访问能力。特别是，哈希表允许我们以O(1)的平均时间复杂度进行元素的查找、插入和删除操作。这对于统计一个数组中每个元素出现的次数尤其有用，因为数组可能包含重复的元素，而哈希表可以快速地更新元素的计数。此外，哈希表能够直接通过元素值作为键来访问计数，这使得数据的组织和后续操作（如排序和遍历频率）更为直观和高效。
这是因为算法的逻辑是优先移除出现频率最低的元素，这样可以最大化地减少不同整数的数量。一旦一个整数的频率比剩余可移除的元素数k还要大，这意味着不能再完全移除更多的整数（因为无法完全去除任何一个整数而不超过剩余的k值）。这样，算法只能停止移除操作，因为任何进一步的移除都将无法完全消除一个整数类别。因此，一旦处理完所有可以完全移除的元素，剩余的k值虽然可能还未用尽，但已无法用于进一步减少不同整数的总数。
算法通过排序元素的频率列表并从最小频率开始移除来确保达到最少不同整数的目标。这种方法是基于这样一个事实：移除频率最低的整数会以最小的‘成本’（即移除的元素数量）减少不同整数的种类。通过从频率最低的元素开始并逐步向上处理，算法确保在每一步都尽可能减少不同整数的数量，直到无法继续移除更多整数或者k被完全消耗。这种策略是贪心算法的一种形式，它在这种情况下可以确保达到问题的最优解。
如果k的值非常大，接近或等于数组的长度，这意味着几乎可以移除数组中的所有元素。在这种极端情况下，算法的一个优化策略可以是先计算整个数组的元素总数，然后与k进行比较。如果k大于或等于数组长度，那么可以直接返回0，因为可以移除所有元素，从而没有任何不同的整数剩余。这种优化避免了不必要的计算和操作，直接根据k的大小和数组长度给出结果，大大提高了算法在极端情况下的效率。