前端 leetcde 算法面试套路之堆
正文 plus
堆是动态求极值的数据结构,所以当遇到需要不断取极值的时候,就可以考虑用堆了
温馨提示,建议每一道题都自己 new 一个堆,这样才能发现堆之美,其实就是不会再次遇到 topK 的时候只能用冒泡来做。
行文至此也该结束了,如果有 10 个关注,那就更新一下下一 part, dp 或者树吧, thx。
二叉堆的创建
分析 -- 小顶堆
这里是一个小顶堆,特点就是根节点的值比子节点的值都小,通常用作经典的前 K 大
主要有两个方法,
一个是上升,这里主要用作构建堆的时候,整理堆用的
一个是下沉,这里主要用于弹出堆顶元素后,置换了堆顶值之后使用的,这里用到 this.data[0],是因为这个方法一般是构建完整的堆之后,才会使用
其他的方法不是不可以,只是为了保证灵活性,暂时就先做个简易版,后面再考虑,因为方法越多,其实兼容性就越差了
分析 -- 大顶堆
相对于初始版的小顶堆,这一版的大顶堆添加了两个方法, pop 和 add
add 方法可以写在使用堆的位置,但是为了让它和堆的第一个值匹配,所以写在了类方法里面,方便对 size 的添加
pop 是为了取出堆顶元素,
堆是为了解决动态取极值
而存在的数据结构,所以必然要取出整理的过程。
215. 数组中的第 K 个最大元素
分析
这是一道炒鸡经典的题,可以用冒泡,快排,其中最经典的方法,莫过于小顶堆求值 -- 作为教材基本的题目
这里求第 K 大,那么就是要维护一个 K 大的小顶堆,然后堆顶就是第 K 大
然后遍历数组 nums,先初始化一个 K 大的小顶堆,然后剩下的值就和堆顶比较;
只要是值大过堆顶值的,那么直接把堆顶值替换掉,但这时,堆顶值就不一定是小顶堆中的最小值了,所以需要向下 down 整理一下小顶堆
遍历结束后就得到一个小顶堆了,然后直接去堆顶元素就是第 K 大了;
时间复杂度: {O(N*L) -- 其中 N 是数组大小, L 是二叉堆的层高,L 其实相对来说比较小,所以复杂度可以说接近线性
空间复杂度: O(M) -- 其中 M 是就是 K 值,因为要维护一个 K 大堆
参考视频:传送门
1046. 最后一块石头的重量
分析 -- 大顶堆
按照题目已经,需要取出一组数组中的最大值和次大值,进行一定运算后,会将计算值返回给数组,然后循环操作,直到数组长度最大为 1 时结束
所以就是动态取极值,可以考虑用堆来处理
定义一个方法 pop,每次获取堆顶元素,并将大顶堆整理好,定义方法 add 为为堆加入元素
这样每一次取出两个元素,返回 1 或 0 个元素,一直到堆元素小于 2 时结束,返回堆中的元素或 0
空间复杂度就是维护堆,所以是 O(N), 时间复杂度 O(NlogN)
23. 合并 K 个升序链表
分析 -- 堆
这里主要是把链表当成是堆的一个元素,以链表头的值作为小顶堆创建的基点
这里要求得到是 K 个升序链表合并链表,我每次都获取 K 个链表中的最小值,然后放到我自己的链表中,最后得到的就是一个合并完的升序链表了
空间复杂度就是维护堆,所以是 O(N∗M), 其中 N 是 lists 的长度, M 是 链表的平均长度
时间复杂度: 取出值合并到新链表 -- O(N∗M)
分析 -- 分治
多个排序链表很难处理,那么两个排序好的链表合并呢?
将两个有序链表合成一个,然后放进 list 继续走,最后合成一个即可
用分治,如果超出 2 个链表,就拆分了处理,mergeKLists(arr) 最后得到的也是一个排序好的链表,所以每次可以分开治,然后最后 merge 治;
合并两个链表的时间复杂度 O(N),分治处理 M 个链表的复杂度为 O(logM) 所以 O(NlogM) , 其中 N 是链表的长度, M 是链表的数量
451. 根据字符出现频率排序
分析
既然是要按照出现评率进行新组装,所以先遍历一次字符串,用 map 将字符和出现频率作为一组 item 保存起来 -- 时间空间复杂度都是 O(N)
这个时候其实只要按照频率从到到小排列好,然后一一取出重装即可
这边是用堆排序,但是 item 不再是简单的数字,而是一个数组 [key,value],所以相应的方法微调即可
堆排是时间复杂度:O(NlogN), 最终的空间复杂度是 O(N)
378. 有序矩阵中第 K 小的元素
分析
这里就是 item 为数组的 bottomK, 和正常的 top K 只是多了以数组作为元素的处理
使用堆排的时候,只需要整理函数 down 和 upper 比对的时候弄一下就好了
不过有一个区别就是,这个 K 有可能大于二维数组的数组长度 Len(matrix), 所以不能直接创建一个 K 大大顶堆取堆顶,反而要将二维数组所有元素都编入到 Len 大小的小顶堆中,然后再取 K 次
这也说明了 top K 这类题的两种堆解法,要不就是设置 K 大/小 的堆,然后不断用元素去替代,要不设置全部元素的堆,然后弹出 K 次值;
时间/空间复杂度 O(NlogN)
1054. 距离相等的条形码
分析
为了保证两两不相等,那得保证数量最多的那个条码必须先排完,防止排完其他就省它自个儿了;
所以先用 map 存储所有条码值(key)和数量(value)
这个时候就和 1046. 最后一块石头的重量很像了;
但是还有一点区别,就是每次你取出最大的两块,都只能取走一份进行排列,然后就要把剩下的放回去,保证每一次取两个值都是最大;这就好比,我们这道题是去磨石头,每次相互之间磨掉一层皮,每一次都要拿最后的石头去磨,而 1046. 最后一块石头的重量 是直接两个一砸就结束了;
map 存储时,时间复杂度和空间复杂度都是 O(N), N 是长度; 堆排,这个算不出来了,大概也是 O(NlogN) 吧
评论