网站设计网站建站,wordpress 表情包,彩票网站开发制作模版,关键词优化ppt1.数组中的第K个最大元素【215】
思路#xff1a; 1.1.要使得时间复杂度为O(n)#xff0c;自己实现大顶堆#xff0c;通过K次调整#xff0c;顶部元素就是想要的第K个最大元素 1.2.实现大顶堆的过程中#xff0c;先建堆#xff0c;建堆是利用递归#xff0c;本…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会自动按照排序器规则调整小顶堆
