使用 next 和 prev 值对列表进行排序 [英] Sorting a list with next and prev values

问题描述

我有具有值 id, next, prev 的对象.其中 next 和 prev 具有其他 id 的值.这些对象的顺序相当随意.我想按照列表中没有前一个对象的对象出现在第一个位置的顺序获取它们，然后是具有第一个对象的下一个值的对象，依此类推.

I have objects that have the values id, next, prev. Where next and prev have an value of an other id. These objects are in an rather arbitrary order. I want to get them in the order that the object, that has no previous object in the list comes at position one, then the object that has the id of the first objects next value and so on.

• 排序函数应该返回一个列表列表
• 如果列表中有无法连接的不同部分，它们将位于两个单独的列表中.(可以这么说:我们有 2 个结局和 2 个开始)
• 0 表示没有上一个/下一个
• 排序函数在复杂性方面应尽可能高效
• 伪代码就可以了，不需要 Javascript

let list = [
{"id": 181, "next": 182, "prev": 231},
{"id": 182, "next": 253, "prev": 181},
{"id": 230, "next": 231, "prev": 0},
{"id": 231, "next": 181, "prev": 230},
{"id": 253, "next": 254, "prev": 182},
{"id": 254, "next": 0, "prev": 253},
]

console.log("unordered", list.map(x => x.id))
let falsesorted = sortByNextPrev(list);
falsesorted.forEach(sub => {
  console.log(sub.map(x => x.id));
});

function sortByNextPrev(list){
 var sorted = list.reduce((acc,l) => {
     let last = acc[acc.length-1];
    if(last.length === 0 || last[last.length-1].next === l.id){
        last.push(l)
    }
    else if(last[0].prev === l.id){
        last.unshift(l);
    }
    else{
        acc.push([l]);
    }
    return acc;
},[[]]);
return sorted;
}

我的功能显然没有达到我想要的效果.我尝试实现的顺序是 230,231,181,182,253,254.

My function obviously does not achieve what I want. The order I try to achieve is 230,231,181,182,253,254.

我试图绕过它，但我还没有找到有效的解决方案.我想我可以构建一个非常愚蠢的函数，但我宁愿不这样做.

I tried to wrap my head around it, but I haven't found an efficient solution. I guess I could build a really stupid function, but I'd rather not.

推荐答案

只需使用查找函数并从第一个元素开始，将它们一个接一个地放入结果数组中.查找可以通过循环、在排序数组中进行二分搜索或使用查找表进行优化来完成.

Just use a lookup function and start with the first element, putting them in the result array one after the other. The lookup could be done stupid simple with a loop, with a binary search in your sorted array, or optimised with a lookup table.

让我们选择最后一种方法，无论如何我们都需要一次迭代才能找到第一个元素:

Let's choose the last approach, we need one iteration to find the first element anyway:

const byId = new Map();
const firsts = [];
for (const el of list) {
    byId.set(el.id, el);
    if (!el.prev) firsts.push(el);
}
const results = firsts.map(first => {
    const result = [];
    for (let x = first; x != null; x = byId.get(x.next))
        result.push(x);
    return result;
});

这篇关于使用 next 和 prev 值对列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！