【笔记】JavaScript版数据结构与算法——基础算法之“排序类”(215. 数组中的第K个最大元素)
2023-09-27 14:26:51 时间
数组中的第K个最大元素
1.题目
- 数组中的第K个最大元素 - 力扣(LeetCode)
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
题目模板
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
};
2.思路分析
见题解
3.所用到的方法
见题解
4.题解及优化
我的题解
不就是排序后找倒数第k个元素么
let findKthLargest = (nums, k) => {
return nums.sort((a, b) => a - b)[nums.length - k]
}
或是倒排取正:
let findKthLargest = (nums, k) => {
return nums.sort((a, b) => b - a)[k - 1]
}
在冒泡排序过程中取值:
let findKthLargest = (nums, k) => {
for (let i = 0; i < k; i++) {
for (let j = nums.length - 1; j > i && j > 0; j--) {
[nums[j], nums[j - 1]] = nums[j] > nums[j - 1] ? [nums[j - 1], nums[j]] : [nums[j], nums[j - 1]]
}
}
return nums[k - 1]
}
。。。性能好差
使用堆排序:
let len // 因为声明的多个函数都需要数列长度,所以把len设置成为全局变量
/**
* 堆调整
* @param arr 需要调整的数组
* @param i 预调整元素下标
*/
let adjustHeap = (arr, i) => {
let left = 2 * i + 1
let right = 2 * i + 2
// arr[i]预调整元素
let max = i
// 下面两步找到左右子树中最大的一个的下标
if (left < len && arr[left] > arr[max]) {
max = left
}
if (right < len && arr[right] > arr[max]) {
max = right
}
// 将左右子树的最大值赋给父节点(里面执行说明min有变动)
if (max !== i) {
[arr[max], arr[i]] = [arr[i], arr[max]]
adjustHeap(arr, max) // 这步递归为确保本枝杈下端的最大值提到当前父端(arr[max])
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
let findKthLargest = function(nums, k) {
len = nums.length
// 构建大顶堆
for (let i = Math.floor(len / 2); i >= 0; i--) {
adjustHeap(nums, i)
}
// 堆排序
for (let i = len - 1; i >= nums.length -k; i--) {
// 将堆顶(树根)置换到相应位置
[nums[0], nums[i]] = [nums[i], nums[0]]
len-- // 此时len表示的是未排序的arr长度
adjustHeap(nums, 0)
}
return nums[nums.length - k]
}
还不错
相关文章
- TypeScript 针对 JavaScript 做了什么
- javascript动态添加一组input
- 轻量函数式 JavaScript:七、闭包 vs 对象
- 【面试算法题】JavaScript 字符串反转的三种方式
- 排序算法 基于Javascript
- Eclipse color theme jsp javascript显示问题
- 【JavaScript】循环获取复选框的值
- JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序
- JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的 ?其数据结构是怎样的 ?(下)
- JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序(上)
- JavaScript 数据结构与算法之美 - 线性表(数组、栈、队列、链表)(上)
- JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(中)
- JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(下)
- 【笔记】JavaScript版数据结构与算法——基础算法之“递归类”(93. 复原IP地址)
- 【笔记】JavaScript版数据结构与算法——基础算法之“数组类”(89. 格雷编码)
- 【笔记】JavaScript版数据结构与算法——基础算法之“数组类”(914. 卡牌分组)
- LightningChart JS Crack,2D 和 3D JavaScript 图表
- 总结面试题——Javascript
- JavaScript的6个算法实用小技巧
- QRCode.js:使用 JavaScript 生成二维码
- JavaScript巧学巧用
- JavaScript使用构造函数获取变量的类型名
- javascript实现有向无环图中任意两点最短路径的dijistra算法
- Javascript算法和数据结构
- javascript算法
- JavaScript数据结构与算法 基础