leetcode 347. Top K Frequent Elements | 347. 前 K 个高频元素（大根堆）-蒲公英云

leetcode 347. Top K Frequent Elements | 347. 前 K 个高频元素（大根堆）

题目

https://leetcode.com/problems/top-k-frequent-elements/
在这里插入图片描述

题解

参考：leetcode 215. Kth Largest Element in an Array | 215. 数组中的第K个最大元素（Java）

class Solution { 
    public static class HeapNode { 
        int num;
        int count;
        public HeapNode(int num, Integer count) { 
            this.num = num;
            this.count = count;
        }
    }
    public int[] topKFrequent(int[] nums, int k) { 
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) { 
            if (!map.containsKey(n)) map.put(n, 1);
            else map.put(n, map.get(n) + 1);
        }
        // 建大根堆
        int heapSize = map.size();
        HeapNode[] heap = new HeapNode[heapSize];
        int j = 0;
        for (int key : map.keySet())
            heap[j++] = new HeapNode(key, map.get(key));
        for (int i = heapSize - 1; i >= 0; i--) // 自下向上建堆 可证复杂度为O(n)
            heapify(heap, i, heapSize);
        // Top k
        int[] result = new int[k];
        int pos = 0;
        for (int i = 0; i < k; i++) { 
            result[pos++] = heap[0].num;
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
        }
        return result;
    }
    public void heapify(HeapNode[] heap, int i, int heapSize) { 
        int left = i * 2 + 1;
        while (left < heapSize) { 
            int largest = left + 1 < heapSize && heap[left + 1].count > heap[left].count ? left + 1 : left; // 左右孩子较大者的下标
            largest = heap[largest].count > heap[i].count ? largest : i; // 两个孩子与父节点较大者的下标
            if (largest == i) break; // 不需要交换的情况
            swap(heap, largest, i);
            i = largest; // 更新i使其下沉
            left = 2 * i + 1;
        }
    }
    private void swap(HeapNode[] heap, int i, int j) { 
        HeapNode tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
}