javascript - K-排序链表算法

Question

我也在 leetcode 上做 k 排序链表。

问题:合并 k 个排序的链表并将其作为一个排序的列表返回。分析并描述其复杂性。

提问链接:https://leetcode.com/problems/merge-k-sorted-lists/submissions/

例子:

输入:

[
  1->4->5,
  1->3->4,
  2->6
]

输出:1->1->2->3->4->4->5->6

这里输入这个

[[1,4,5],[1,3,4],[2,6]]

实际上看起来像这样(通过时)

[ ListNode { val: 1, next: ListNode { val: 4, next: [ListNode] } },
  ListNode { val: 1, next: ListNode { val: 3, next: [ListNode] } },
  ListNode { val: 2, next: ListNode { val: 6, next: null } } ]

所以无论如何，我写了这段代码

 // converts input array to object
const arrayToObject = (lists) => {
    if (lists.length === 0) return lists 
    else {
        let linkedListMergedArray = []
        for (let i=0; i<lists.length; i++) {
            const itterationItem = lists[i]
            const reduceToArray = recursivelyCreateArray(itterationItem)
            if (reduceToArray) linkedListMergedArray = [...linkedListMergedArray, ...reduceToArray ]
        }
     return linkedListMergedArray
    }
}
// breaks down the object to linkedList 
const recursivelyCreateArray = (listObject) => {
    if (!listObject) return null
    if (Array.isArray(listObject)) return arrayToObject(listObject)
    if (!listObject.next) return [listObject.val]
    else return [listObject.val, ...recursivelyCreateArray(listObject.next)]
}

// creates an object which looks like { val: value, next { val: value
const convertMergedArrayToOutputLinkedList = (mergedArray, i=0) => {
    if (!mergedArray[i]) return null
    else return {
        val: mergedArray[i],
        next: convertMergedArrayToLinkedList(mergedArray, i+1)
    }
}

//starting point of code
var mergeKLists = function(lists) {
 const linkedListToArray = arrayToObject(lists)
 if (linkedListToArray.length > 0) {
     const sortArray = linkedListToArray.sort((a,b) => a-b)
     return convertMergedArrayToOutputLinkedList(sortArray)
 } else return null
};

但是这对于跟随输入是失败的[[0,2,5]]

同时，我仍在调试它，我觉得这不是最佳算法，所以有人可以帮助我编写优化代码，并找出我可能做错了什么吗？

Answer 1

简单的方法

一个明显的解决方案是简单地合并所有列表，然后对结果进行排序。 O(nlogn)。值得注意的是，在现实中，这几乎是一条没有太多麻烦的单线航线。

    function ez(heads){
        function toArr(l){
            v=[]
            while(l){v.push(l.val); l=l.next}
            return v;
        }
        return heads.map(toArr).flatMap(l=>l).sort((a,b)=>a-b)
    }

更快的方式

如果你想要 moar 性能，(O(n))

假设您有三个游标(每个列表一个)。

在时间 t，您选择光标指向的最小元素。然后将该光标移动到其列表的下一个元素。转到。

您显然在每个列表的开头初始化了游标。

    function linear(heads){
        function min(heads){//inspect all cursors and get the min
            let idx = -1;
            let val = 9000;
            for(let i = 0; i<heads.length; ++i){
                if(heads[i] && heads[i].val<val){
                    val = heads[i].val;
                    idx = i;
                }
            }
            return {idx, val}
        }
        let stack = [];
        while(true){
            let {idx, val}=min(heads);
            if(idx == -1){
                break
            }
            stack.push(val);
            heads[idx] = heads[idx].next; //move the cursor.
        }
        return stack;
    }

验证

最后在这里检查理论上更快的方法确实更快并不麻烦:

    function ez(heads){
        function toArr(l){
            v=[]
            while(l){v.push(l.val); l=l.next}
            return v;
        }
        return heads.map(toArr).flatMap(l=>l).sort((a,b)=>a-b)
    }
    function linear(heads){
        function min(heads){
            let idx = -1;
            let val = 1000;
            for(let i = 0; i<heads.length; ++i){
                if(heads[i] && heads[i].val<val){
                    val = heads[i].val;
                    idx = i;
                }
            }
            return {idx, val}
        }
        let stack = [];
        while(true){
            let {idx, val}=min(heads);
            if(idx == -1){
                break
            }
            stack.push(val);
            heads[idx] = heads[idx].next
        }
        return stack;
    }
    
    let arr = [
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b),
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b),
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b)
];
//just create the linked lists
let heads = arr.map(x=>x.reduce((acc,val)=>{
    acc.cur.next = {val, next:null}
    if(acc.head == null){
        acc.head = acc.cur.next
    }
    acc.cur = acc.cur.next;
    return acc;
},{head:null, cur:{}})).map(x=>x.head)
console.time('ez')
ez(heads)
console.timeEnd('ez'); //4ms for me
console.time('linear')
linear(heads)
console.timeEnd('linear'); //2ms for me

---

我建议您测试不同的尺寸，您会注意到 ez 方式更快，直到达到某个长度。