友链
姚屹晨

leetcode - [1481] Least Number of Unique Integers after K Removals

2020/06/18

问题描述

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

给你一个整数数组，和一个整数k，经过k次删除后，请计算数组中剩余最少唯一的整数数量。

举个例子：

解法1

Thanks @rock and @usamaten

首先，我们需要构建一个Map，其中key为出现的唯一元素，value为是其出现的次数。

然后，还需要构建一个最小堆，存储数组中出现的唯一元素，并根据频率进行递增排列。

来看下示意图：

如何做到？

PriorityQueue<Object> pq = new PriorityQueue<>((a, b) -> (map.get(a) - map.get(b)));

优化一下：

PriorityQueue<Object> pq = new PriorityQueue<>(Comparator.comparing(map::get));

接着，我们开始计算最小数量：

注意，当k = 4时，等它遍历完PriorityQueue中的前四个元素，它的值是多少？

k = -1。因为，元素2出现了2次。

所以，最后我们需要对k进行判断，如果k < 0，说明有个元素还有"残余"，就算你删了，也没用，

所以我们的返回结果为pq.size() + 1，否则，正常返回pq.size()。

来看下实现：

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        int len = arr.length;
        HashMap<Integer, Integer> map = new HashMap<>(len);
        for (int i: arr){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<Object> pq = new PriorityQueue<>(Comparator.comparing(map::get));
        pq.addAll(map.keySet());
        
        while (k > 0){
            k -= map.get(pq.poll());
        }
        return k < 0 ? pq.size() + 1 : pq.size();

    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory