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

布满荆棘的人生 2022-08-30 00:49 162阅读 0赞

## 题目 ##

[https://leetcode.com/problems/top-k-frequent-elements/][https_leetcode.com_problems_top-k-frequent-elements]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

参考：[leetcode 215. Kth Largest Element in an Array | 215. 数组中的第K个最大元素（Java）][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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_top-k-frequent-elements]: https://leetcode.com/problems/top-k-frequent-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/8785a529f143438c9941ed8dc20a5c0a.png
[leetcode 215. Kth Largest Element in an Array _ 215. _K_Java]: https://blog.csdn.net/sinat_42483341/article/details/117920376
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/e34d630e7bfc4d42a6fda6a6a4a6d8bb.png