购物类网站,wordpress国内最流行的主题,济阳建设局网站,企业网站托管新趋势1. 题目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素#xff0c;请找出移除后数组中不同整数的最少数目。
示例 1#xff1a;
输入#xff1a;arr [5,5,4], k 1
输出#xff1a;1
解释#xff1a;移除 1 个 4 #xff0c;数组中只剩下 5 一…1. 题目
给你一个整数数组 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/least-number-of-unique-integers-after-k-removals 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
map计数把数量排序取出前面个数少的能尽可能多的取出不同的种类
class Solution { //C
public:int findLeastNumOfUniqueInts(vectorint arr, int k) {unordered_mapint,int m;int i;for(i 0; i arr.size(); i)m[arr[i]];vectorint count(m.size());i 0;for(auto it m.begin(); it ! m.end(); it)count[i] it-second;sort(count.begin(), count.end());i 0;while(k 0){k - count[i];if(k 0)i;}return count.size()-i;}
};432 ms 61.2 MB
class Solution:# py3def findLeastNumOfUniqueInts(self, arr: List[int], k: int) - int:d {}for i in arr:if i in d:d[i] 1else:d[i] 1count list(d.values())# count.sort()count sorted(count)i 0for c in count:k - cif k 0:i 1if k 0:breakreturn len(count) - i120 ms 26.8 MB
