theme: cyanosis
highlight: atom-one-dark
开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第8天,点击查看活动详情
- 239.滑动窗口最大值
- 347.前K个高频元素
239.滑动窗口最大值
题目链接:239. 滑动窗口最大值 – 力扣(LeetCode)
给你一个整数数组
nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k
个数字。滑动窗口每次只向右移动一位。(注意:1 <= k <= nums.length
)返回 滑动窗口中的最大值 。
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7]
我的解法(超时)
针对题目给的例子,可以得到期望的答案,但是提交代码就会超出时间限制。应该是时间复杂度太高了。
- 定义好队列后,先找出一个滑动窗口大小的数组,放进队列中。这里考虑用for循环了,稍后会总结一波数组拷贝的内容。
- 设置一个循环,不断执行以下步骤:取得窗口中的最大值,然后窗口向右移动一位。
var maxSlidingWindow = function (nums, k) {
let queue = [];
let res = [];
// 先选出第一个窗口
for (let i = 0; i < k; i++) {
queue.push(nums[i])
}
console.log(queue);
for (let j = k; j < nums.length; j++) {
res.push(Math.max(...queue));
queue.shift();
queue.push(nums[j]);
}
res.push(Math.max(...queue));
return res
};
看了官方的解释,
对于长度为 n 的数组 nums 而言,窗口的数量为 n−k+1,因此该算法的时间复杂度为
O((n−k+1)k)=O(nk)
,会超出时间限制,因此我们需要进行一些优化。
卡神解法
本题算比较有难度的,需要自己去构造单调队列,建议先看视频来理解。视频中说。自己去编写一个队列,实现队列中的元素单调递增或者单调递减
我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
主要思想是队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。
var maxSlidingWindow = function (nums, k) {
class MonoQueue {
queue;
constructor() {
this.queue = [];
}
enqueue(value) {
let back = this.queue[this.queue.length - 1];
while (back !== undefined && back < value) {
this.queue.pop();
back = this.queue[this.queue.length - 1];
}
this.queue.push(value);
}
dequeue(value) {
let front = this.front();
if (front === value) {
this.queue.shift();
}
}
front() {
return this.queue[0];
}
}
let helperQueue = new MonoQueue();
let i = 0, j = 0;
let resArr = [];
while (j < k) {
helperQueue.enqueue(nums[j++]);
}
resArr.push(helperQueue.front());
while (j < nums.length) {
helperQueue.enqueue(nums[j]);
helperQueue.dequeue(nums[i]);
resArr.push(helperQueue.front());
i++, j++;
}
return resArr;
};
拿例子 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 来解释
-
首先执行
let helperQueue = new MonoQueue();
helperQueue 是 MonoQueue 构造出来的实例对象。接着执行 class 中的构造函数,知道了对象 helperQueue.queue 是数组。 -
while (j < k) { helperQueue.enqueue(nums[j++]); }
- 首先 j 为 0 ,在不断 while 的过程中,通过实例对象中的 enqueue 方法,在 num 中将滑动窗口区域的元素,进行一个处理,然后放到 helperQueue.queue 中。怎么处理的呢?
- 将当前取得的 nums 中的元素记为 value 。先判断队列中最后一个数(back) 是否存在,如果存在那么和当前的 value 比较值的大小。当 value 更大一点的时候,就删除最后一个数,然后back又变为新数组的最后一个数。之后就把数值更大一点的 value 压入数组中。
- 那么经过此次 while 过后
- 可见数组里面的数是单调递减的,前面第一个元素就是我们需要的窗口内的最大值。可以通过实例对象的内置方法
front()
返回第一个元素,同时也删除了第一个元素。
-
接下来的 while 就是不断滑动窗口,此时 i = 0, j = 2
- 那么目前右移,遇到的就是 -3 了,首先还是执行
enqueue()
来判断能否进入队列。同样的,-3 加到了数组的最后,[3, -1, -3] 没有破坏单调性。 helperQueue.dequeue(nums[i]);
这个时候 i 开始发挥作用了,此时 nums[i] = 1 。进入到函数 dequeue 中,则value就是 1 。貌似针对本例子,第一次调用这个函数没什么太大的作用? 但是再仔细想想,之前的步骤中处理完的窗口,数组已经是[3, -1]了,那就算经过上一步的enqueue()
过后,数组为[3, -1, -3] ,那就不需要处理滑动窗口左边的数了。这也就理解大佬文章中写的 如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
- 那么目前右移,遇到的就是 -3 了,首先还是执行
-
由此可以看到,虽然题目说了滑动窗口的大小为 k ,但是这一题我们通过设置一个单调递减的双头队列,就能得到想要维护的动态窗口,窗口长度是小于等于 k 的。
347.前K个高频元素
题目链接:347. 前 K 个高频元素 – 力扣(LeetCode)
给你一个整数数组
nums
和一个整数k
,请你返回其中出现频率前k
高的元素。你可以按 任意顺序 返回答案。输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
我的解法
以下代码通过没有AC,那为啥贴在这里?当然是为了分析咯😜
先讲一下我的思路吧:
- 统计数组中的字符出现次数,并且转为对象map
- 定义一个 max ,用来统计出现次数中的最大值。遍历 map 中的 key ,得到其出现的次数,当次数大于 max 时,就更新 max 为当前 key 所对应的最大值。
- 由于要找出前 k 个,所以循环 k 次。每次找到的最大值压入结果 res 里面,完了后删除map中所找到的这个结果,这样下次遍历的时候不会重复找出这个最大值。
// 统计数组中的字符出现次数,并且转为对象
var strToObj = function(arr) {
let obj = {};
for(let i = 0; i < arr.length; i++) {
let item = arr[i]; // chars是字符串的每一个字符
if(obj[item]) {
obj[item]++;
} else {
obj[item] = 1;
}
}
return obj
}
var topKFrequent = function(nums, k) {
let res = [];
let map = strToObj(nums);
while (k--) {
let max = 0; // 每次都重新计数
for (var key in map) {
if (map[key] > max) {
max = map[key];
res.push(parseInt(key))
map[key] = undefined;
// console.log(map);
}
}
}
console.log(res);
return res
};
// @lc code=end
// let nums = [1, 1, 1, 2, 2, 3], k = 2;
let nums = [4,1,-1,2,-1,2,3], k = 2;
topKFrequent(nums, k)
对于第一个例子nums = [1, 1, 1, 2, 2, 3], k = 2;
是可以得到理想结果的。但是对于nums = [4,1,-1,2,-1,2,3], k = 2;
期望得到的是[-1,2] ,实际得到的是[ 1, 2, 3, -1 ]。
思路想法我觉得是可行的,虽然代码有点多且杂。。。
问题出在了while循环语句里面,for...in...
结构里面的语句。拿出错的例子来说,第一个遍历到的是 key: 1, value:1 此时已经大于max了,所以就被压入res里面了。后续的话,虽然 while 循环进行了k次,但是每次里面的 for 循环就压入了好几个数。由此,最后的结果出现的有的多!
改进:改动while循环里面的结构,上面代码中的strToObj()
就不在这里重复写了。这个版本的代码通过率为100%
var topKFrequent = function(nums, k) {
let res = []; // 存放结果
// 统计数组中每个数字出现的次数
let map = strToObj(nums);
let maxNum; // map中的键,也就是数字
while (k--) {
let max = 0; // 出现的最大次数
for (var key in map) {
if (map[key] > max) {
max = map[key];
maxNum = parseInt(key);
}
}
res.push(maxNum)
map[maxNum] = undefined
}
return res
};
卡神解法
大顶堆和小顶堆,这种数据结构特别擅长在一个很大的数据集里面求前k个高频或者低频之类的结果。
大顶堆:每个结点的值都大于或等于其左右孩子结点的值。 小顶堆:每个结点的值都小于或等于其左右孩子结点的值。
普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组,且不使用指针
js 没有堆 需要自己构造,具体解法可以看链接。
总结
-
有一个很好用的,统计数组(或者字符串)中元素(或字符)出现的次数,在这里封装成函数,方便下次复用。
var strToObj = function(arr) { let obj = {}; for(let i = 0; i < arr.length; i++) { let item = arr[i]; // chars是字符串的每一个字符 if(obj[item]) { obj[item]++; } else { obj[item] = 1; } } return obj }
-
JavaScript中
for of
能否遍历对象? 不能,但是for in
是为遍历对象属性而构建的 -
对象的长度不能用.length获取
获取方式:
var length = Object.keys(obj).length;
-
对象中删除某个属性,可以让该属性的值变为 undefined 。
参考文章
- ES6 copyWithin – 掘金 (juejin.cn)
- Array对象方法(四)concat/copyWithin – 掘金 (juejin.cn)
- js排序的时间复杂度js十大排序算法weixin_39627052的博客-CSDN博客
- 优先级队列_百度百科 (baidu.com)
- 优先级队列*-木云-的博客-CSDN博客*优先级队列
- 剑指Offer——I.滑动窗口的最大值(JS实现) – 掘金 (juejin.cn)
- for…of 和 for…in 是否可以直接遍历对象,有什么解决方案 – 我叫大王来巡山 – 博客园 (cnblogs.com)
- js删除对象的某个属性我的小本本的博客-CSDN博客js删除对象中的某个属性
- js获取对象的长度viceen的博客-CSDN博客js获取对象的长度
- JS获取对象长度大小!大雷!的博客-CSDN博客js 对象长度
- 堆排序(浅谈大顶堆与小顶堆)END_Last的博客-CSDN博客大顶堆小顶堆的定义
暂无评论内容