5454. Least Number of Unique Integers after K Removals

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

---

给定一个数组，问从中删掉K个数后，剩余数中unique数的个数最少是多少。

要让剩余的unique数最少，则删掉的数必须是频率最低的数。举个例子，原数组是[1,2,3,3,3]，如果删掉两个数，肯定是删掉1,2，这样剩余是[3,3,3]，unique数只有3这一个数。如果删掉两个3，则剩余[1,2,3]，unique数有3个。

所以，对所有数按其频率从小到大排序，然后删掉频率最低的前几个数即可。完整代码如下：

class Solution {
public:
	int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
		int n = arr.size();
		vector<pair<int, int>> num_counts;
		unordered_map<int, int> hash;
		for (int i = 0; i < n; ++i)++hash[arr[i]];
		for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
			num_counts.push_back(make_pair(it->second, it->first));
		}
		sort(num_counts.begin(), num_counts.end());
		int m = num_counts.size(), sum = 0;

		if (k == 0)return m;
		else if (k == n)return 0;

		for (int i = 0; i < m; ++i) {
			sum += num_counts[i].first;
			if (sum == k)return m - i - 1;
			else if (sum > k)return m - i;
		}

		return 0;
	}
};

本代码提交AC，用时792MS。