Given an array of integers
arr
and an integerk
. Find the least number of unique integers after removing exactlyk
elements.Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left.
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.
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
- mine
-
Java
Runtime: 56 ms, faster than 50.00%, Memory Usage: 88.8 MB, less than 50.00% of Java online submissions
//O(N)time O(N)space public int findLeastNumOfUniqueInts(int[] arr, int k) { Map<Integer, Integer> map = new HashMap<>(); //record element count int[] res = new int[arr.length + 1]; for (int a : arr) { int t = map.getOrDefault(a, 0); if (t != 0) { //let count is t down res[t]--; } map.put(a, t + 1); //let count is t+1 up res[t + 1]++; } int count = 0; for (int i = 1; i < res.length; i++) { if (res[i] == 0) { continue; } //res[i] is element count is i; //so res[i] * i is the element count is i int c = res[i] * i; if (k >= c) { k -= c; } else { //[3,3,3] 2 //remove k/i = 2 / 3 = 0 count += res[i] - k / i; k = 0; } } return count; }
-