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: Greedy
Count the frequency of each unique number. Sort by frequency, remove items with lowest frequency first.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int findLeastNumOfUniqueInts(vector<int>& arr, int k) { unordered_map<int, int> c; for (int x : arr) ++c[x]; vector<int> m; // freq for (const auto [x, f] : c) m.push_back(f); sort(begin(m), end(m)); int ans = m.size(); int i = 0; while (k--) { if (--m[i] == 0) { ++i; --ans; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment