在 O(n) 中将数组缩减为 sub-array

Question

考虑数据来源：

const data: InfoNode[] = [
    {
        parentId: '7',
        id: '1',
        name: 'Harry'
    },
    {
        parentId: '7',
        id: '2',
        name: 'Hermoine'
    },
    {
        parentId: '7',
        id: '3',
        name: 'Ron'
    },
    {
        parentId: '2',
        id: '4',
        name: 'Voldemort'
    },
    {
        parentId: '2',
        id: '5',
        name: 'Snape'
    },
    {
        parentId: '8',
        id: '6',
        name: 'Hagrid'
    },
    {
        parentId: '6',
        id: '7',
        name: 'Dumbledore'
    },
    {
        parentId: '10',
        id: '8',
        name: 'Malfoy'
    },
    {
        parentId: '10',
        id: '9',
        name: 'Sirius Black'
    },
    {
        parentId: null,
        id: '10',
        name: ' JK Rowling'
    }
]

现在这个数据源的层次结构是这样的（parent 是 JK Rowling）：

JK Rowling -> Malfoy, Sirius Black, Hagrid, Dumbledore, Harry, Hermoine, Ron, Voldemort, Snape

我必须将其缩减为具有特定 parent id 及其所有 children 的新数组。说，如果我传递 id 6（parent 变成 Hagrid）它应该 return 我的数组像：

Hagrid -> Dumbledore, Harry, Hermoine, Ron, Voldemort, Snape

复杂度为 O(n^2) 的解决方案可用 here。

注意：新数组的排序顺序无关紧要。

想知道是否可以在 O(n) 中完成。

Answer 1

要实现线性时间复杂度，您需要一个 hashmap，它为插入和查找提供 O(1)（摊销）时间复杂度。

想法是首先将树信息转换为邻接表，其中条目由 id 键控。获得邻接列表后，您可以递归向下钻取以查找给定 ID 的所有后代。

这是 JavaScript 中的一个实现：

function buildAdjacencyList(data) {
    // Create objects with children property, and key them by id
    const adj = Object.fromEntries(data.map(o => [o.id, { ...o, children: [] }]));
    // Add a sentinel entry for having the root as child
    adj[null] = { children: [] };
    // Populate the children arrays based on parent relationships
    for (const o of data) adj[o.parentId].children.push(o.id);
    return adj;
}

function * descendants(adj, id) {
    yield adj[id].name;
    for (let childId of adj[id].children) {
        yield * descendants(adj, childId)
    }
}

// Demo
const data = [ { parentId: '7', id: '1', name: 'Harry' }, { parentId: '7', id: '2', name: 'Hermoine' }, { parentId: '7', id: '3', name: 'Ron' }, { parentId: '2', id: '4', name: 'Voldemort' }, { parentId: '2', id: '5', name: 'Snape' }, { parentId: '8', id: '6', name: 'Hagrid' }, { parentId: '6', id: '7', name: 'Dumbledore' }, { parentId: '10', id: '8', name: 'Malfoy' }, { parentId: '10', id: '9', name: 'Sirius Black' }, { parentId: null, id: '10', name: ' JK Rowling' } ];

const adj = buildAdjacencyList(data);
for (const name of descendants(adj, '6')) {
    console.log(name);
}

在 O(n) 中将数组缩减为 sub-array

Reduce array to sub-array in O(n)

algorithm

tree

typescript