【Javascript】“前K个”类问题总结

本文主要是介绍【Javascript】“前K个”类问题总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

近日刷题碰到一道题：

LeetCode 215.

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

这个题很简单，先排序，后输出前k个元素即可。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  nums.sort((a, b) => b - a)
  return nums[k-1]
};

但当我打开相似题目时，好家伙

 依次点开题后，再“相似”一下

好家伙，这是一类题呀！一狠心，干脆就全刷了！

刷完之后也总结出来的核心玩法：非升序排序=>.slice(0, k) 即可。

当然也有更复杂的情况：

【情况1】对于词频的统计，可以先用 map 统计所有词频，然后根据词频排序即可。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  const map = new Map()
  for (let num of nums) map.set(num, (map.get(num) || 0) + 1)
  const arr = Array.from(map.keys())
  arr.sort((a, b) => map.get(b) - map.get(a))
  return arr.slice(0, k)
};

【情况2】对于数据流，由于不断更新，因此要使用堆的方法，不断更新排序堆。

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
  this.k = k
  this.arr = new Array(k).fill(-Infinity)
  for (let num of nums) this.add(num)
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
  let temp = val
  for (let i=0; i<this.k; ++i) if (temp > this.arr[i]) [this.arr[i], temp] = [temp, this.arr[i]]
  return this.arr[this.k - 1]
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */

 关于“前K”这类题的总结基本就完成了，此时相似题中居然还有不是“前K”的——“摆动排序”。

LeetCode 324.摆动排序II：给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

有II必然有I，我又打开了

LeetCode 280.摆动排序： 给你一个无序的数组 nums, 将该数字 原地 重排后使得 nums[0] <= nums[1] >= nums[2] <= nums[3]...。

一开始，我甚至没有发现这两个题目的区别，想着先逐个击破吧。这是280题的解答：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function(nums) {
  for (let i=0, n=nums.length; i<n-1; ++i) 
    if ((i & 1) == (nums[i] < nums[i+1])) [nums[i], nums[i+1]] = [nums[i+1], nums[i]]
};

解完还挺沾沾自喜的，毕竟这相当于是一行代码解决问题。然后开始解324题，直接复制代码，不好使！甚至琢磨了很久都没有找到原因，然后可耻的我居然去偷看答案。。。这里竟然发现了宝藏，我苦苦不解的题目居然有人一行就完成了？然后我就顺理成章的 copy 了代码 23333

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function(nums, left = nums.length+1>>1, right = nums.length) {
  nums.slice().sort((a, b) => a - b).forEach((val, i, arr) => nums[i] = i & 1 ? arr[--right] : arr[--left]) // 这里的 val 是用不上的， arr 为引用的原数组
};

仔细看看这个题解，分为三部：

1、浅拷贝 nums.slice()；

2、非降序排序 sort((a, b) => a - b)；

3、重新赋值，这里需要细说一下：

3.1、forEach 方法的三个参数 (val, i, arr) （当前值，当前索引，当前原数组）。在这之前，从没考虑过第三个参数居然还有这样的用法，毕竟一般都是 arr.forEach 这么调用的，没考虑过在调用的时候可能原数组本身就是拷贝出来的，并没有赋值，arr 这个参数就可以直接取到原数组！

3.2、然后就是对于题设的理解，从排序好的数组中段分开，按次排放就能达到题设效果。

没想到刷一个题竟牵扯出这么多，其中有很多细节都在解题的过程中，收获最大的可能就是对 forEach 方法更深的理解！

不过还有个不解的地方，在数据流的题目里，官方有一个关于 MinPriorityQueue 类的定义，这里先埋下一个坑，希望之后的学习里能让有机会得到解答。

（第一次记录自己的学习经历，也算是激励自己，学习有时候真的很苦乏，希望自己能一直坚持下去！）

这篇关于【Javascript】“前K个”类问题总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！