给你一个整数数组 arr 和一个整数 k 。现须要从数组中刚好移除 k 个元素,请找出移除后数组中不一样整数的最少数目。python
示例 1:数组
输入:arr = [5,5,4], k = 1
输出:1
解释:移除 1 个 4 ,数组中只剩下 5 一种整数。
示例 2:网络
输入:arr = [4,3,1,1,3,3,2], k = 3
输出:2
解释:先移除 四、2 ,而后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个,最后剩下 1 和 3 两种整数。
code
提示:排序
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.lengthleetcode
来源:力扣(LeetCode)
连接:https://leetcode-cn.com/problems/least-number-of-unique-integers-after-k-removals
著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。rem
思路:get
根据贪心的思想,留下的元素里重复元素应该越多越好,也就是说优先保留重复次数最多的元素。io
因此不妨把全部元素的出现次数从大到小进行排序,再判断能留几个不一样整数。ast
时间复杂度:O(NlogN)
空间复杂度:O(N)
class Solution(object): def findLeastNumOfUniqueInts(self, arr, k): """ :type arr: List[int] :type k: int :rtype: int """ from collections import Counter if not arr or len(arr) == k: return 0 l = Counter(arr).values() l = sorted(l)[::-1] target = len(arr) - k s = 0 for i, num in enumerate(l): s += num if s >= target: return i + 1