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.
1from collections import Counter
2
3def least_number_of_unique_ints(arr, k):
4 freq = Counter(arr)
5 frequencies = sorted(freq.values())
6 unique_count = len(frequencies)
7 for f in frequencies:
8 if k >= f:
9 k -= f
10 unique_count -= 1
11 else:
12 break
13 return unique_count
14
15arr = [4, 3, 1, 1, 3, 3, 2]
16k = 3
17print(least_number_of_unique_ints(arr, k))The Python solution uses the Counter from the collections module to count frequencies. The frequencies are then sorted to facilitate selective removal, maintaining a count of unique items efficiently.
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 Java solution involves counting the frequency of each integer using a HashMap, then sorting these frequencies to allow removal of the least frequent elements first, thus achieving the minimum count of unique integers.