LeetCode 5437. 不同整數的最少數目

題目

給你一個整數數組 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^5

1 <= arr[i] <= 10^9

0 <= k <= arr.length

解題思路

class Solution:
    def findLeastNumOfUniqueInts(self, arr: [int], k: int) -> int:
        import collections
        countDic = dict(collections.Counter(arr).most_common())
        # print(countDic)
        # retList = list(countDic)
        # print(retList)
        # return len(set(retList[k:]))
        resKeyList = list(countDic.keys())
        resKeyList.reverse()
        for i in resKeyList:
            count = countDic[i]
            k -= count
            if k >= 0:
                countDic.pop(i)
                # print(countDic)
            if k < 0:
                break
        return len(countDic)