215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题
零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(215)数组中的第K个最大元素
一 题目描述
文章图片
二 解法总览(思维导图)
文章图片
三 全部解法
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 历史文章 - 总览
文章图片
文章图片
2 博主简介 【215、数组中的第K个最大元素|215、数组中的第K个最大元素 | 算法(leetcode,附思维导图 + 全部解法)300题】码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~
推荐阅读
- javaSE|二叉树——二叉查找树、平衡二叉树(红黑树)
- 算法|二叉树、二叉搜索树、AVL树、B树、红黑树
- 用 Python 做“贪吃蛇”,在线吃不饱
- SQL|SQL Server中实现错误处理
- python中数组array和列表list的基本用法及区别解析
- vue|vue入门--js高阶函数(箭头函数)、v-model数据绑定、组件化、父子组件通信及访问
- 将EditText数组转换为字符串数组 - Kotlin Android
- c语言哪种编译器能够单步调试,02、老徐教你学C语言基础篇2——C语言摩拳擦掌齐上阵(环境篇)——调试工具及调试技巧...
- 调试技巧——C语言下BEBUG调试开关
- Amazon Personalize 个性化效果评估,从准确性到多样性、新颖性和偶然性