【学习打卡】第26天 数据结构和算法
2022/9/1 4:22:48
本文主要是介绍【学习打卡】第26天 数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
堆
合并K个升序链表(leetcode - 23)
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例
输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
思路
- 创建一个最小堆,将链表数组的每个链表头部插入堆中
- 循环最小堆,将堆顶出堆,将堆顶的下一个链表插入堆中
- 堆为空时循环结束,返回指针的头部
class MinHeap { constructor() { this.heap = []; } swap(i1, i2) { const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(index) { return Math.floor((index - 1) / 2); } getLeftIndex(index) { return index * 2 + 1; } getRightIndex(index) { return index * 2 + 2; } shiftUp(index) { if (index === 0) return const parentIndex = this.getParentIndex(index); if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) { this.swap(index, parentIndex); this.shiftUp(parentIndex) } } shiftDown(index) { if (index === this.heap.length - 1) return; const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) { this.swap(index, leftIndex); this.shiftDown(leftIndex); } if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) { this.swap(index, rightIndex); this.shiftDown(rightIndex); } } insert(val) { this.heap.push(val); this.shiftUp(this.heap.length - 1); } pop() { if(this.size() === 1) return this.heap.shift(); const top = this.heap[0]; this.heap[0] = this.heap.pop(); this.shiftDown(0); return top; } peek() { return this.heap[0]; } size() { return this.heap.length; } } /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { const res = new ListNode(0); const h = new MinHeap(); let p = res; lists.forEach(l => { if(l) h.insert(l) }); while(h.size()) { const n = h.pop(); p.next = n; p = p.next; if(n.next) h.insert(n.next); } return res.next; };
复杂度分析:
时间复杂度:O(nlogk)
空间复杂度:O(k)
这篇关于【学习打卡】第26天 数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)