原文链接: https://leetcode-cn.com/problems/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

中文题目

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

 

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

 

提示：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

通过代码

高赞题解

有点类似 前 K 个高频元素 那道题的做法
先使用 哈希表 来统计所有的数字出现频次
然后将其 存入 优先队列 最小堆
接着 每次都从 堆顶删.

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        int n = arr.size();
        unordered_map<int, int> m;
        for (int i = 0; i < n; i ++) {
            m[arr[i]] ++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (auto x : m) {
            pq.push({x.second, x.first});
        }
        while (k && pq.size()) {
            auto t = pq.top();
            if (k >= t.first) {
                k -= t.first; 
            } else {
                break;
            }
            pq.pop();
        }
        return pq.size(); 
    }
};

统计信息

通过次数	提交次数	AC比率
10535	20443	51.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言