Formatted question description: https://leetcode.ca/all/1481.html
1481. Least Number of Unique Integers after K Removals (Medium)
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
Solution 1.
// OJ: https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/
// Time: O(N + UlogU) where U is the number of unique counts
// Space: O(N)
class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& A, int k) {
unordered_map<int, int> cnt;
for (int n : A) cnt[n]++;
map<int, int> m;
for (auto &p : cnt) m[p.second]++;
int ans = cnt.size();
for (auto &p : m) {
int n = min(p.second, k / p.first);
if (n == 0) break;
ans -= n;
k -= p.first * n;
}
return ans;
}
};
Java
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> numCountMap = new HashMap<Integer, Integer>();
for (int num : arr) {
int count = numCountMap.getOrDefault(num, 0) + 1;
numCountMap.put(num, count);
}
List<Integer> list = new ArrayList<Integer>();
Set<Integer> numSet = numCountMap.keySet();
for (int num : numSet)
list.add(numCountMap.get(num));
int unique = 0;
Collections.sort(list);
int remain = arr.length - k;
for (int i = list.size() - 1; i >= 0 && remain > 0; i--) {
int count = list.get(i);
remain -= count;
unique++;
}
return unique;
}
}