1481.Least Number of Unique Integers after K Removals¶
Tags: Medium
Array
Sort
Links: https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/
Given an array of integers arr
and an integer k
. Find the least number of unique integers after removing exactly k
elements**.**
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
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.
Constraints:
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
贪心+哈希表+排序。
用哈希表统计不同数字的个数,用数组seq
存储每个数字对应的个数,然后对seq
进行排序,为了让最后不同的数字种类最少,肯定是从数量少的开始删除才会得到最优解。
最坏的情况是数周内的数字都不相同,时间复杂度O(n \log n)。
class Solution {
vector<int> seq;
unordered_map<int, int> um;
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (const auto & e : arr) ++um[e];
for (const auto & e : um) seq.push_back(e.second);
sort(seq.begin(), seq.end());
int n = seq.size();
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (seq[i] <= k) {
++cnt;
k -= seq[i];
}
else {
k = 0;
}
if (k == 0) break;
}
return n - cnt;
}
};