Sponsored
Sponsored
This approach involves two main steps. First, count the frequency of each integer in the array. Second, use a min-heap (or priority queue) to remove the integers with the smallest frequency first. This approach ensures that we are removing the least frequent integers to reach the least number of unique integers efficiently.
Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.
1import java.util.*;
2
3public class Solution {
4 public int findLeastNumOfUniqueInts(int[] arr, int k) {
5 Map<Integer, Integer> frequencyMap = new HashMap<>();
6 for (int num : arr) {
7 frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
8 }
9
10 List<Integer> frequencyList = new ArrayList<>(frequencyMap.values());
11 Collections.sort(frequencyList);
12
13 int uniqueCount = frequencyList.size();
14 for (int freq : frequencyList) {
15 if (k >= freq) {
16 k -= freq;
17 uniqueCount--;
18 } else {
19 break;
20 }
21 }
22
23 return uniqueCount;
24 }
25
26 public static void main(String[] args) {
27 Solution solution = new Solution();
28 int[] arr = {4, 3, 1, 1, 3, 3, 2};
29 int k = 3;
30 System.out.println(solution.findLeastNumOfUniqueInts(arr, k));
31 }
32}This Java solution leverages a HashMap for maintaining frequency counts of elements. The frequencies are stored in a List and sorted to guide removals. By iterating through the sorted list, it decrements the unique count effectively.
This approach takes a greedy strategy to count frequencies of integers and sorts them. By progressively removing elements with smallest frequencies, it directly calculates the least number of unique integers remaining after exactly k removals.
Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.
This implementation in C uses a frequency array to count each integer's occurrences. After sorting this array, elements are removed from the smallest frequency upwards until k removals are exhausted.