挑戰：
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
我將把我的代碼放在下面，但簡要介紹一下我的解決方案：
- 為原始陣列中的每個串列創建一個包含節點的排序雙向鏈表，其中每個節點包含頭節點的值和該節點所在的陣列索引
- 在雙向鏈表頭節點指示的索引處彈出單鏈表頭節點，并附加到結果串列的尾部
- 洗掉雙向鏈表的頭部并插入一個新節點，表示剛剛彈出的串列的新頭部
- 一直持續到雙向鏈表為空
我認為這實際上不是一種非常有效的方法。在最壞的情況下，將一個節點插入雙向鏈表是 O(k)。每次從一個單鏈表中彈出一個節點時，我都會在串列中插入一個新節點，所以如果 n 是每個單鏈表的平均長度，那不會使我的整體時間復雜度 O(k * (k*n)) = O(nk^2)？如果是這樣，我想知道我如何沒有超過這些限制的時間限制：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
無論如何，這是我的（Typescript）代碼，其中包含運行所需的所有驅動程式功能：
// nodes of the singly-linked lists given by the challenge
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
}
// nodes for the doubly-linked list I used to keep track of what order
// in which to pop from the singly-linked lists
class OrderNode {
headVal: number
listIndex: number
next: OrderNode | null
prev: OrderNode | null
constructor(val: number, i: number, next: OrderNode | null, prev: OrderNode | null) {
this.headVal = val
this.listIndex = i
this.next = next === undefined ? null : next
this.prev = prev === undefined ? null : prev
}
}
// typescript bs
function nullFilter<TValue>(value: TValue | null | undefined): value is TValue {
if (value === null || value === undefined) return false
const test: TValue = value
return true
}
// main function
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const filtered = lists.filter(nullFilter)
if (!filtered.length) return null
// create initial doubly-linked list
let order: OrderNode = insert(null, filtered[0], 0)
for (let i = 1; i < filtered.length; i ) {
order = insert(order, filtered[i], i)
}
let remaining: OrderNode | null = order
// set up initial variables for while loop
const firstI = remaining.listIndex
const firstNode = filtered[firstI]
let head: ListNode | null = push(null, firstNode)
let tail: ListNode | null = head
const firstInsert = shiftList(filtered, firstI)
remaining = shiftOrder(remaining)
if (firstInsert) {
remaining = insert(remaining, firstInsert, firstI)
}
// main while loop
while (remaining) {
const i = remaining.listIndex
// get node to push to end of result list
const pushNode = filtered[i]
// shift that node and get the new head
const newHead = shiftList(filtered, i)
// shift the head of the order list
remaining = shiftOrder(remaining)
// if there are nodes left in the popped list, add the new head to the order list
if (newHead) {
remaining = insert(remaining, newHead, i)
}
tail = push(tail, pushNode)
}
return head
}
// push a node to the end of the result list
function push(tail: ListNode | null, node: ListNode): ListNode {
const newNode = new ListNode(node.val, null)
if (tail) {
tail.next = newNode
}
return newNode
}
// insert a new node into the sorted list keeping track of order
function insert(head: OrderNode | null, node: ListNode, i: number): OrderNode {
const newNode = new OrderNode(node.val, i, null, null)
if (!head) {
return newNode
} else {
if (node.val <= head.headVal) {
head.prev = newNode
newNode.next = head
return newNode
} else {
let temp: OrderNode | null = head
let prev: OrderNode | null = null
while (temp) {
if (temp.headVal >= node.val) break
prev = temp
temp = temp.next
}
prev = prev as OrderNode
if (temp) {
prev.next = newNode
newNode.prev = prev
newNode.next = temp
temp.prev = newNode
return head
} else {
prev.next = newNode
newNode.prev = prev
return head
}
}
}
}
// shift the head from the order list
function shiftOrder(head: OrderNode | null): OrderNode | null {
if (head) {
if (head.next) {
const newHead = head.next
newHead.prev = null
return newHead
} else {
return null
}
} else {
return null
}
}
// shift a node from one of the given lists, and return the new head
function shiftList(lists: Array<ListNode | null>, i: number): ListNode | null {
let currentHead = lists[i]
if (currentHead) {
lists[i] = currentHead.next
return lists[i]
} else {
return null
}
}
// driver code
const input: number[][] = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
]
const lists = input.map(array => {
let next = null
for (let i = array.length - 1; i >= 0; i--) {
next = new ListNode(array[i], next)
}
return next
})
let result = mergeKLists(lists)
while (result) {
process.stdout.write(`${result.val} -> `)
result = result.next
}
uj5u.com熱心網友回復：
至少有兩種“計算機科學”方法可以做到這一點：
使用堆而不是雙向鏈表，它允許您彈出（并重新插入1）在其頭節點中具有最小值的串列。
1如果堆實作提供了替換（交換）方法，則使用該方法代替單獨的彈出和推送操作。成對合并串列，因此串列的數量會減少（同時它們的大小會增加），直到只剩下一個串列。為了提高效率，這應該通過分治演算法（遞回）來完成，每次通過將串列陣列分成兩半來解決合并問題，直到只剩下一個串列作為基本情況。然后——在回溯時——對從遞回回傳的兩個串列執行合并。
我將在可運行的 JavaScript 片段中演示第二個解決方案：
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
// main function
function mergeKLists(lists) {
// Divide and conquer
if (lists.length < 2) return lists[0]; // Base case
const i = lists.length >> 1; // Half
const pair = [mergeKLists(lists.slice(0, i)), mergeKLists(lists.slice(i))];
// Merge pair of non-empty lists:
const head = popLeast(pair);
let tail = head;
while (pair[0] && pair[1]) {
tail = tail.next = popLeast(pair);
}
tail.next = pair[0] ?? pair[1]; // Attach the remainder
return head;
}
function popLeast(pair) {
const i = pair[0].val < pair[1].val ? 0 : 1;
const least = pair[i];
pair[i] = least.next;
return least;
}
// Helper functions for I/O
function stringify(head) {
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return nodes.join(" -> ");
}
function createList(values) {
let head = null;
for (const val of values.reverse()) {
head = new ListNode(val, head);
}
return head;
}
// driver code
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));這比使用雙向鏈表的解決方案具有更好的時間復雜度：它是 O(nklogk) 而不是 O(nk2)。
應該提到的是，當您將所有內容轉換為陣列并對其執行排序時，JavaScript 非常快。但是這種練習旨在以最少的空間使用來解決（不包括您需要創建或列印串列的部分）
uj5u.com熱心網友回復：
正如 trincot 的回答中所述，這是一個堆版本。
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
var k = lists.length;
heap(lists); // convert to min heap
const head = lists[0]; // merged list = list[0]
var tail = head;
while (true) {
lists[0] = lists[0].next; // lists[0] = next node
if (lists[0] == null) { // if end of lists[0]
if(--k == 0) // reduce heap size
break;
lists[0] = lists[k]; // lists[0] = last list
}
sift(lists, 0, k); // fix heap
tail = tail.next = lists[0]; // append node to merged list
}
return head;
}
function heap(lists) { // convert lists to min heap
var i = (lists.length-1)/2;
while (i >= 0) {
sift(lists, i, lists.length);
i--;
}
}
function sift(lists, i, k) { // sift lists[i] down
var m = i;
while (true) {
i = m;
var l = 2*i 1;
var r = 2*i 2;
if(l < k && lists[l].val < lists[i].val)
m = l;
if(r < k && lists[r].val < lists[m].val)
m = r;
if(m == i)
break;
[lists[i], lists[m]] = [lists[m], lists[i]];
}
}
// Helper functions for I/O
function stringify(head) {
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return nodes.join(" -> ");
}
function createList(values) {
let head = null;
for (var val of values.reverse()) {
head = new ListNode(val, head);
}
return head;
}
// driver code
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));
非遞回成對合并版本，使用小陣列 ar[] 而不是堆疊，其中 ar[i] == null 或 ar[i] = 2^i 個串列的合并。
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
if (lists.length < 2) return lists[0];
const sz = Math.ceil(Math.log2(lists.length 1));
const ar = new Array(sz).fill(null);
var mg = null;
var i, j;
for (j = 0; j < lists.length; j ) {
// merge lists[j] into ar[]
mg = lists[j];
for (i = 0; ar[i] != null; i ) {
mg = merge(ar[i], mg);
ar[i] = null;
}
ar[i] = mg;
}
// merge ar[] into single list
for (i = 0; ar[i] == null; i );
mg = ar[i];
for ( i ; i < sz; i )
if (ar[i] != null)
mg = merge(ar[i], mg);
return mg;
}
function merge(l0, l1) {
var pair = [l0, l1];
var head = popLeast(pair);
var tail = head;
while (pair[0] && pair[1])
tail = tail.next = popLeast(pair);
tail.next = pair[0] ?? pair[1];
return head;
}
function popLeast(pair) {
const i = pair[0].val < pair[1].val ? 0 : 1;
const least = pair[i];
pair[i] = least.next;
return least;
}
// Helper functions for I/O
function stringify(head) {
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return nodes.join(" -> ");
}
function createList(values) {
let head = null;
for (const val of values.reverse()) {
head = new ListNode(val, head);
}
return head;
}
// driver code
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446399.html
上一篇：基于柏林噪聲的點隨機分布？
下一篇：調整二維矩陣大小的基本演算法