微信制作网站开发,建设网站主题,合肥电子网站建设,网站建设高职考题目java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路#xff1a;时间复杂度O( n n n)#xff0c;空间复杂度…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路时间复杂度O( n n n)空间复杂度O( l o g 2 n log_2{n} log2n) 使用小根堆建堆时间复杂度O(k),调整堆(删除堆顶并插入新元素)O( n ∗ l o g 2 k n*log_2k n∗log2k),其中k是题目要求的返回第k最大元素。因此小根堆大小为k故建堆为O(k). 共计O( k n ∗ l o g 2 k kn*log_2k kn∗log2k) O(n)不断地将元素插入到小根堆根最小其它元素都比根大中当堆中有k个元素此时还需要往堆中插入元素时需要进行判断。因为此时堆顶元素正好是堆中倒数第k大元素。如果新插入元素比堆顶大。证明当前堆顶不是倒数第k大则堆顶删除并将新元素插入。此时调整堆新的堆顶元素为第k大。以此类推。直到所有元素入堆后。最终返回堆顶即可。 堆排序https://blog.csdn.net/grd_java/article/details/136937525
代码:当前官方增加了很多测试用例已经无法超越100%的用户了目前最快的算法只能达到17ms进行优化后也只到了15ms。我查看2021年提交时的记录是3ms超越100%。目前已经无法达到了。 使用Java提供的优先级队列实现小根堆面试时候肯定不让你用。因此这个代码帮你理解整体的思路。然后第二个实现方法我们需要自己实现小根堆 class Solution {//[6,5]//public int findKthLargest(int[] nums, int k) {PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger() {//返回值0,o1放在o2后面。反之o1放o2前面//小根堆小的在前面。利用o1-o2实现。如果o1小o1-o20o1会放在o2前面//如果o1大o2小o1-o20,o1会放在o2后面。而小的o2放在o1前面Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for(int num:nums){if(queue.size() k){if(queue.peek() num) {queue.poll();queue.offer(num);}}else{queue.offer(num);}}return queue.poll();}
}自己实现小根堆因为Java自带容器加了很多健壮性和线程安全的逻辑所以效率较慢我们自己实现小根堆就会快很多。 class Solution {public int findKthLargest(int[] nums, int k) {int[] minHeap new int[k];//小根堆for (int i 0; i k; i) {//大小为kminHeap[i] nums[i];}//k/2-1是二叉树的知识代表以k个结点构成的二叉树的第一个非叶子结点。k/2-2是第二个非叶子以此类推。i 0是整个二叉树的根结点for (int i k / 2 - 1; i 0; i--) {//调整小根堆从下到上依次让每一颗子树满足小根堆adjustHeap(minHeap, i);//i是二叉树的每个非叶子结点小根堆的要求是每个子树根结点都是整棵树最小}//小根堆构建完成后minHeap[0]就是当前第k大的数。接下来需要不断进行判断和入堆操作for (int i k; i nums.length; i) {if (nums[i] minHeap[0]) {//如果当前i是比小根堆堆顶更大的元素那么堆顶不是第k大minHeap[0] nums[i];//将堆顶出堆并将i放在堆顶位置adjustHeap(minHeap, 0);//此时很有可能小根堆逻辑被破坏也就是i太大不满足小根堆因此需要让i进行下降调整让其重新满足小根堆定义}}return minHeap[0];}/*** 以root为根结点构建/调整堆* param array 堆* param root 当前根结点*/private void adjustHeap(int[] array, int root) {//让root结点下降到合适位置以满足小根堆效果任何一颗子树根结点都是最小的while (true) {//当堆调整完成后结束int left 2 * root 1;//获得root的左子结点下标int right left 1;//获得root的右子结点下标int min root;//最小值最终需要放到root结点位置//如果左子结点存在并且左子结点更小让min指向这个结点if (left array.length array[left] array[min]) min left;//如果右子结点存在并且右子结点更小让min指向这个结点if (right array.length array[right] array[min]) min right;//如果min root说明小根堆调整结束if (min root) break;//让min当前指向位置和root交换也就是下降操作说明root当前指向的结点不是最小值不满足小根堆//因为小根堆越上面层次的结点越小所以如果当前root太大需要让其下降swap(array, root, min);//root本次下降完成后min的位置是root新的位置。因为root下降到min的位置//让root指向min然后继续循环判断是否root需要继续下降。直到它下降到合适位置root min;}}private void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;}
}
