LeetCode 1481: Least Number of Unique Integers after K Removals
Problem Description
Explanation
To solve this problem, we can follow these steps:
- Count the frequency of each integer in the array.
- Sort the integers based on their frequencies.
- Remove the least frequent integers one by one until we have removed
kelements. - Return the count of unique integers remaining after removal.
Time complexity: O(n log n) where n is the number of integers in the array. Space complexity: O(n) to store the frequency of each integer.
Solutions
import java.util.*;
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
List<Integer> freqList = new ArrayList<>(freqMap.values());
Collections.sort(freqList);
int uniqueCount = freqList.size();
int count = 0;
for (int freq : freqList) {
if (k >= freq) {
k -= freq;
count++;
} else {
break;
}
}
return uniqueCount - count;
}
}Loading editor...