Day05
算法每日一题
原题链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=problem-list-v2&envId=2cktkvj
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
/**
* 快速排序的变种，用于查找数组中第 k 大的元素
* @param {number[]} nums - 要排序的数组
* @param {number} left - 当前排序范围的左边界
* @param {number} right - 当前排序范围的右边界
* @param {number} k - 要查找的第 k 大元素的索引（从 0 开始）
* @return {number} - 返回数组中第 k 大的元素
*/
let q_sort = function(nums, left, right, k) {
let i = left, j = right;
// 选择中间元素作为基准
let mid = nums[(left + right) >> 1];
// 分区操作
while (i <= j) {
// 从左向右找到第一个小于等于基准的元素
while (nums[i] > mid) i++;
// 从右向左找到第一个大于等于基准的元素
while (nums[j] < mid) j--;
// 交换元素并移动指针
if (i <= j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
j--;
}
}
// 递归调用左半部分
if (left < j && k <= j) {
return q_sort(nums, left, j, k);
// 递归调用右半部分
} else if (i < right && k >= i) {
return q_sort(nums, i, right, k);
// 找到第 k 大的元素
} else {
return nums[k];
}
}
/**
* 查找数组中第 k 大的元素
* @param {number[]} nums - 要查找的数组
* @param {number} k - 第 k 大的元素
* @return {number} - 返回数组中第 k 大的元素
*/
var findKthLargest = function(nums, k) {
// 注意 k-1，因为数组索引从 0 开始
return q_sort(nums, 0, nums.length - 1, k - 1);
};
这道题其实会快速排序的话思路还是很容易出来的，具体来说，在快速排序的过程中，我们只需要判断当前的基准元素是否已经是我们要找的第 k 大元素。如果是的话，我们就不需要继续对其他元素进行分治处理了，因为此时基准元素左边的所有元素都比它大，右边的所有元素都比它小。因此，基准元素的位置就是我们要找的第 k 大元素的位置，我们可以直接返回这个元素。
另外说一下快排的思路，快速排序是一种基于分治法的高效排序算法。它的基本思想是通过一趟排序将待排序的数组分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素要小，然后再对这两部分分别进行递归排序。具体步骤如下：
1.选择基准（Pivot）： 从数组中选择一个元素作为基准。常见的选择方法有：
- 选择第一个元素
- 选择最后一个元素
- 选择中间元素
- 随机选择一个元素
2.分区（Partition）： 将数组重新排列，使得所有比基准小的元素都放在基准的左边，所有比基准大的元素都放在基准的右边。分区完成后，基准元素位于其最终的位置。
3.递归排序： 递归地对基准左边和右边的子数组进行快速排序。
前端学习记录
webpack5内置了clean属性可以自动清空上次打包的内容，对于iconfont的文件可以使用type: "asset/resource"，会原封不动的输出打包内容
// Node.js的核心模块，专门用来处理文件路径
const path = require("path");
module.exports = {
// 入口
// 相对路径和绝对路径都行
entry: "./src/main.js",
// 输出
output: {
// path: 文件输出目录，必须是绝对路径
// path.resolve()方法返回一个绝对路径
// __dirname 当前文件的文件夹绝对路径
path: path.resolve(__dirname, "dist"),
// filename: 输出文件名
filename: "main.js",
clean: true, // 自动清空上次打包内容
},
// 加载器
module: {
rules: [
{
test: /\.css/, // 匹配css文件的正则表达式
use: ["style-loader", "css-loader"], // 执行顺序是从右往左执行 css-loader 再执行 style-loader
},
{
test: /\.(png|jpg|JPG|gif)/, // 匹配图片文件的正则表达式
type: "asset", // 类型是asset
// 解析器
parser: {
dataUrlCondition: { // 小于8kb的图片会被base64处理
maxSize: 8 * 1024,
}
},
generator: { // 输出图片文件的名称
// [name] 取文件名 [ext] 取文件扩展名
// [hash:6] 取图片的hash值的前6位
filename: "images/[name].[hash:6][ext]",
}
},
{
test: /\.(eot|ttf|woff2?)$/, // 匹配字体文件的正则表达式
type: "asset/resource", // 类型是asset/resource
generator: { // 输出字体文件的名称
filename: "fonts/[name].[hash:6][ext]",
}
}
],
},
// 插件
plugins: [],
// 模式
mode: "development", // 开发模式
};