厦门建设管理局网站首页品牌推广外包

1.数组中的第K个最大元素【215】

思路：
        1.1.要使得时间复杂度为O(n)，自己实现大顶堆，通过K次调整，顶部元素就是想要的第K个最大元素

        1.2.实现大顶堆的过程中，先建堆，建堆是利用递归，本质上是从下到上地进行大顶堆的调整，因为如果从上到下，只能实现局部的大顶堆，有可能会漏掉一些元素没调整

        1.3.叶子节点本身就满足大顶堆的性质，所以不需要调整，只需要从倒数第2排进行调整即可，即heapSize / 2 - 1

        1.4.对于某个堆进行调整的时候，判断左子树2 * i + 1，右子树 2 * i + 2，和根节点i，如果左右子树有比i的值大的，取更大的作为largest最大节点，与根节点进行交换，并且递归地调整largest位置的子树符合大顶堆的性质。注意！！交换的只是值，但是largest索引没变，其子树还是原来位置的子树

2. 前K个高频元素

思路:
        2.1. 先用哈希表对元素以及元素出现的次数进行存储，之后对value即出现次数进行排序即可

        2.2.要求算法时间复杂度优于O(nlogn)，我采用堆排序，利用PriorityQueue优先队列，定义排序器规则，实现小顶堆。由此，最小的元素在队列首部

        2.3.取前K个高频元素，因此优先队列实现的堆的大小为K即可

        2.4.有新的元素来的时候，如果大小小于K，就直接进入队列；否则，如果小顶堆顶部元素小于新的元素，则将顶部元素弹出，新元素进入队列。且PriorityQueue会自动按照排序器规则调整小顶堆