LeetCode每日一题:最小的k个数(七十八)
程序员文章站
2022-07-02 11:04:46
...
最小的k个数
一、LeetCode题解
瞧一瞧~
- 博健的LeetCode题解:Gitbook版本传送门
- 博健的LeetCode题解:CSDN传送门
- 有趣的CSS:Gitbook传送门
- 前端进阶笔记:Gitbook传送门
做题路线( ** = 当前阶段)
- 阶段一(题库+每日一题(3.15日开始每天死磕))**
- 阶段二(解题质量至上)
- 阶段三(算法思想至上)
二、算法题
题目
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
限制:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
解法一 (排序)
思路
-
将数组排序后,取前k个即可
-
时间复杂度:O(n\log n),其中 nn 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
-
空间复杂度:O(\log n),排序所需额外的空间复杂度为 O(\log n)O(logn)。
代码
var getLeastNumbers = function(arr, k) {
arr = quickSort(arr).slice(0,k)
return arr
};
function quickSort(arr) {
if (!Array.isArray(arr)) return;
if (arr.length <= 1) return arr;
var left = [],
right = [];
var num = Math.floor(arr.length / 2);
var numValue = arr.splice(num, 1)[0];
for (var i = 0; i < arr.length; i++) {
if (arr[i] > numValue) {
right.push(arr[i]);
} else {
left.push(arr[i]);
}
}
return [...quickSort(left), numValue, ...quickSort(right)]
}
结果
解法二(大顶堆)
思路
- 创建一个堆,将前k个数插入堆中
- 维护这个堆,保证当前堆内最大的元素在堆顶
- k个之后的元素与堆顶元素比较,如果 < 堆顶元素则进行替换,并重新维护堆保证堆顶元素最大
- 时间复杂度:O(nlogn)
代码
var getLeastNumbers = function(arr, k) {
var res = arr.slice(0, k)
for (let i = k; i < arr.length; i++) {
res = heapSort(res)
if (arr[i] <= res[k-1]) {
res[k-1] = arr[i]
}
}
return res
};
// 交换两个节点
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// 将 i 结点以下的堆整理为大顶堆,注意这一步实现的基础实际上是:
// 假设 结点 i 以下的子堆已经是一个大顶堆,shiftDown函数实现的
// 功能是实际上是:找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环,从第一个非叶子结点开始,对每一个非叶子结点
// 都执行 shiftDown操作,所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function shiftDown(A, i, length) {
let temp = A[i]; // 当前父节点
// j<length 的目的是对结点 i 以下的结点全部做顺序调整
for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
temp = A[i]; // 将 A[i] 取出,整个过程相当于找到 A[i] 应处于的位置
if (j + 1 < length && A[j] < A[j + 1]) {
j++; // 找到两个孩子中较大的一个,再与父节点比较
}
if (temp < A[j]) {
swap(A, i, j) // 如果父节点小于子节点:交换;否则跳出
i = j; // 交换后,temp 的下标变为 j
} else {
break;
}
}
}
// 堆排序
function heapSort(A) {
// 初始化大顶堆,从第一个非叶子结点开始
for (let i = Math.floor(A.length / 2 - 1); i >= 0; i--) {
shiftDown(A, i, A.length);
}
// 排序,每一次for循环找出一个当前最大值,数组长度减一
for (let i = Math.floor(A.length - 1); i > 0; i--) {
swap(A, 0, i); // 根节点与最后一个节点交换
shiftDown(A, 0, i); // 从根节点开始调整,并且最后一个结点已经为当
// 前最大值,不需要再参与比较,所以第三个参数
// 为 i,即比较到最后一个结点前一个即可
}
return A
}
上一篇: 深度解密拼多多在推广中运用的消费心理学
下一篇: Python爬虫 —— 百度翻译
推荐阅读
-
LeetCode每日一题:最小的k个数(七十八)
-
【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)
-
跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题不是leetcode题每次移动一个数字排序
-
【10月打卡~Leetcode每日一题】530. 二叉搜索树的最小绝对差(难度:简单)
-
LeetCode每日一题 (38) 530. 二叉搜索树的最小绝对差 (中序遍历)
-
【LeetCode每日一题】[简单]530. 二叉搜索树的最小绝对差
-
LeetCode每日一题 530. 二叉搜索树的最小绝对差
-
Leetcode 面试题40. 最小的k个数
-
leetcode:那些年我遇到过的编程题006:最小的k个数
-
Leetcode每日一题:530.minimum-absolute-difference-in-bst(二叉搜索树的最小绝对值)