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