美文网首页
算法笔记之堆求取前N个元素

算法笔记之堆求取前N个元素

作者: 简单一点点 | 来源:发表于2020-11-15 11:35 被阅读0次

堆(heap)是一种特殊的数据结构,它通常被看作是一棵树的数组对象,堆总是一颗完全二叉树。

堆分为最大堆和最小堆,在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。

堆经常使用的场景:

  • 构建优先队列
  • 堆排序
  • 快速找出一个集合中的前N大(小)的值

Leetcode347. 前 K 个高频元素

问题概述:给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

解题思路:相当与找出一个集合中前 k 大的值。

Java语言中的优先队列 PriorityQueue 就是使用堆实现的,我们可以使用优先队列解决本题。

Java代码:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            numMap.put(nums[i], numMap.getOrDefault(nums[i], 0) + 1);
        }

        // 优先队列,自定义排序方式
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for(Map.Entry<Integer, Integer> entry : numMap.entrySet()) {
            if(queue.size() < k) {
                queue.offer(new int[] {entry.getKey(), entry.getValue()});
            } else {
                int min = queue.peek()[1];
                if(min < entry.getValue()) {
                    queue.poll();
                    queue.offer(new int[] {entry.getKey(), entry.getValue()});
                }
            }
        }

        int[] result = new int[k];
        for(int i = 0; i < k; i++) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}

Leetcode 692. 前K个高频单词

问题概述:给一非空的单词列表,返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。

解题思路:和上题类似,只是排序方式发生了变化。

Java代码:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> frequentMap = new HashMap<String, Integer>();
        for(int i = 0; i < words.length; i++) {
            frequentMap.put(words[i], frequentMap.getOrDefault(words[i], 0) + 1);
        }
        PriorityQueue<String> queue = new PriorityQueue<String>(
            new Comparator<String>() {
                @Override
                public int compare(String a1, String a2) {
                    int b = frequentMap.get(a1) - frequentMap.get(a2);
                    if(b != 0) {
                        return b;
                    } else {
                        return -a1.compareTo(a2);
                    }
                }
            }
        );
        for(Map.Entry<String, Integer> entry : frequentMap.entrySet()) {
            queue.offer(entry.getKey());
            if(queue.size() > k) {
                queue.poll();
            }  
        }

        List<String> result = new ArrayList<String>();
        while(!queue.isEmpty()) {
            result.add(queue.poll());
        }
        Collections.reverse(result);

相关文章

  • 算法笔记之堆求取前N个元素

    堆(heap)是一种特殊的数据结构,它通常被看作是一棵树的数组对象,堆总是一颗完全二叉树。 堆分为最大堆和最小堆,...

  • TOP N 问题求解 大数据量的情况下

    此算法的复杂度为O(nlogN) n所有元素,N表示堆元素,也就是待查找的元素个数 示例参考 https://ww...

  • [python] n个数中K个最小值

    code: 最大堆假设数组长度为N,首先取前K个数,构建二叉堆(大顶堆),然后将剩余N-K个元素,依次与堆顶元素进...

  • (11)Go实现的最小堆求前K个最大值

    在1,000,000个数字中,选出前100个最大的数字// 在n个元素中选出前m个元素// 如果用排序算法,最快时...

  • 找到最大或最小的N个元素

    本系列来自python cookbook 思路 可以用最大(最小)堆。假设现在要找N个最大的元素,则首先把前N个元...

  • TopN问题

    从1000个数中选择前50个大的数 TopN问题:堆排序思想:先从数组中选出前n个元素组成小根堆。然后遍历后续元素...

  • iOS/OC:插入排序与选择排序的比较

    选择排序(Selection sort)是最基本的O(n^2)的排序算法,通过依次比较数组中前一个元素跟后一个元素...

  • topk 问题

    排序后取前 K 个 算法复杂度 O(nlogn) 遍历 K 遍 算法复杂度 O(kn) k 跟元素的小/大根堆 算...

  • 插入排序

    1 .算法思想 插入排序是最简单的排序算法之一。假定要将n个元素 a[0], a[1], · · · , a[n ...

  • 模拟题 08 Knuth 一个公平的洗牌算法

    1 公平的洗牌算法 公平的理解n个元素,排列可能性 n!, 公平的洗牌算法 应该等概率给出这n!个结果中的任意一个...

网友评论

      本文标题:算法笔记之堆求取前N个元素

      本文链接:https://www.haomeiwen.com/subject/wolnbktx.html