215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题

零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(215)数组中的第K个最大元素 一 题目描述 215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

二 解法总览(思维导图) 215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

三 全部解法 1 方案1 1)代码:

// 方案1 “排序 - 下标定位法(自己)”。// 思路: // 1)将 nums 降序。 // 2)返回 nums 上的 第k个。 var findKthLargest = function(nums, k) { // 1)将 nums 降序。 nums = nums.sort((a, b) => b - a); // 2)返回 nums 上的 第k个。 return nums[k - 1]; }

2 方案2 1)代码:
// 方案2 “不完全的冒泡法(自己)”。// 思路: // 1)状态初始化:l = nums.length; 。 // 2)核心:2层for循环,i范围为 [0, k), j范围为 [i + 1, l) 。 // 2.1)永远保证前 i 个是降序排序的。 // 3)返回结果:数组中的第K个最大元素(即 nums[k - 1] )。 var findKthLargest = function(nums, k) { // 1)状态初始化:l = nums.length; 。 const l = nums.length; // 2)核心:2层for循环,i范围为 [0, k), j范围为 [i + 1, l) 。 for (let i = 0; i < k; i++) { for (j = i + 1; j < l; j++) { // 2.1)永远保证前 i 个是降序排序的。 if (nums[i] < nums[j]) { [nums[i], nums[j]] = [nums[j], nums[i]]; } } }// 3)返回结果:数组中的第K个最大元素(即 nums[k - 1] )。 return nums[k - 1]; }

3 方案3 1)代码:
// 方案3 “基于堆排序的选择方法”。 // 参考: // 1)https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/xie-gei-qian-duan-tong-xue-de-ti-jie-yi-kt5p2/// 思路: // 1)状态初始化,l = nums.length; heapSize = nums.length; 。 // 2)构建好1个大顶堆。 // 3)继续进行 k - 1 次的“大顶堆的构建”。 // 4)返回结果 nums[0] // 注:此时已进行了 k 次的大顶堆的构建,所有 nums[0] 上就是 第k大 的。 var findKthLargest = function(nums, k) { // 自下而上的构建1棵大顶堆 const buildMaxHeap = (nums = [], heapSize = 0) => { for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { maxHeapify(nums, i, heapSize); } }; // 从左向右,自上而下的调整节点 const maxHeapify = (nums = [], index = 0, heapSize = 0) => { const left = 2 * index + 1, right = 2 * index + 2; let largestIndex = index; if(left < heapSize && nums[left] > nums[largestIndex]){ largestIndex = left; } if(right < heapSize && nums[right] > nums[largestIndex]){ largestIndex = right; }if (largestIndex !== index) { // 进行节点调整 swap(nums, index, largestIndex); // 继续调整下面的非叶子节点(递归) maxHeapify(nums, largestIndex, heapSize); } }; const swap = (nums = [], i = 0,j = 0) => { const temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }; // 1)状态初始化,l = nums.length; heapSize = nums.length; 。 const l = nums.length; let heapSize = nums.length; // 2)构建好1个大顶堆。 buildMaxHeap(nums, heapSize); // 3)继续进行 k - 1 次的“大顶堆的构建”。 // 进行下沉 大顶堆是最大元素下沉到末尾。 // 注:“数组中的第K个最大元素”,故 i >= l - k + 1 即可。 for (let i = l - 1; i >= l - k + 1; i--) { // 因为之前建好了大顶堆 swap(nums, 0, i); --heapSize; // 重新调整大顶堆 maxHeapify(nums, 0, heapSize); }// 4)返回结果 nums[0] // 注:此时已进行了 k 次的大顶堆的构建,所有 nums[0] 上就是 第k大 的。 return nums[0]; };

四 资源分享 & 更多 1 历史文章 - 总览 215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

2 博主简介 【215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题】码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~

    推荐阅读