按其相对位置对数组进行排序

Question

示例对象数组:

[{
    id: 'a',
    beforeId: null
}, {
    id: 'b',
    beforeId: 'c'
}, {
    id: 'c',
    beforeId: 'a'
}, {
    id: 'd',
    beforeId: 'b'
}]

输出顺序:d-b-c-a; 每个元素根据其beforeId属性相对于每个其他元素进行排序.

我可以创建一个临时数组并对上面的数组进行排序.可以分类array.sort吗？

Answer 1

您可以使用关系构建一个对象,并通过使用对象和生成beforeId: null结果数组的所有对象来生成结果.

下一个对象是具有实际val键的那个对象.

复杂性:O(2n).

function chain(array) {
    var o = {}, pointer = null, result = [];

    array.forEach(a => o[a.beforeId] = a);

    while (o[pointer]) {
        result.unshift(o[pointer]);
        pointer = o[pointer].val;
    }

    return result;
}

var data = [{ val: 'a', beforeId: null }, { val: 'b', beforeId: 'c' }, { val: 'c', beforeId: 'a' }, { val: 'd', beforeId: 'b' }];

console.log(chain(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }