开发者问题收集

计算数组中的（子）元素数量

2016-02-09
4268
javascript arrays

我有一个对象数组。每个对象如下所示： 

{text: 'foo': level: N: children: M}

N 和 M 都是数字。 N 表示对象所在的“深度”（将整个数组想象成一棵树的表示）。 M 是该项目拥有的子项总数。 Total 表示所有子层级的所有节点和叶子的总和。

我拥有的数组中的对象不包含 children 属性，因此我必须计算它。

“计算”数据的示例： 

{text: 'A': level: 0: children: 0}
{text: 'B': level: 0: children: 1}
{text: 'C': level: 1: children: 0}
{text: 'D': level: 0: children: 2}
{text: 'E': level: 1: children: 1}
{text: 'F': level: 2: children: 0}

A
B
|--C
D
|--E
   |--F

我可以轻松执行 for 循环，然后再对项目进行一次迭代，从数组中的当前位置开始并计算子节点（基于 level 属性），但我觉得这不是最好的（即“最快”）方法。

我还能怎么做？

只是为了确保没有人发布比我目前拥有的“更糟糕”的代码，这就是我拥有的： 

for (var i = 0; i < data.length; i++) {
    var item = data[i];

    for (var j = i + 1; j < data.length; j++) {
        if (item.level < data[j].level) {
            item.children++;
        } else {
            break;
        }
    }
}
3个回答

在当前的示例中，您根本 无法 计算子级，因为您的数据未显示父级/子级关系。例如，对于 text: 'C' ， level:1 如果应将其附加（即增加 children 计数器）到 A 、 B 或 D ，则没有数据。

如果您的意思是，但忘记提及子对象应附加到最近提到的任何最近的父级，则只需保留一个数组，其中每个条目都对应于对该级别最后看到的父元素的引用，并在读取每一行新行后直接使用 += 修改其 chlildren 属性。

Oleg V. Volkov
2016-02-09

我认为@Oleg V. Volkov 在他的评论中提出了这个答案。我认为这是解决问题的一个非常好的方法，而且非常快，因为您只查看每个元素 1 次。然而，缺点是，由于父级数组的存在，它在计算时可能会占用更多的内存。 

function countChildren(tree) {
    var currentParents = [];

    for (var i = 0; i < tree.length; i++) {
        // Initialize value of children
        tree[i].children = 0;

        if (i == 0) {
            continue;
        }

        // Find if the level increased, decreased, or stayed the same.
        var levelChange = tree[i].level - tree[i-1].level;

        // If level increased (by 1)
        if (levelChange == 1) {
            // Add previous element to list of parents
            currentParents.push(tree[i-1]);

        // If level decreased by 'x'
        } else if (levelChange < 0) {
            // Remove 'x' number of elements from the end of the list of parents
            for (var j = 0; j > levelChange; j--) {
                currentParents.pop();
            }
        }

        // Increase the number of children for all parents
        for (var j = 0; j < currentParents.length; j++) {
            currentParents[j].children++;
        }
    }
}
4castle
2016-02-09

这是一种不同于其他所有解决方案的方法，从底层开始。

其优点是，每当达到较小的级别时，就会取和并将实际级别累加器设置为零。

此解决方案仅具有一个循环和一个用于级别累积的数组 count 。

我用这些数据做了一个更大的测试（属性 children 除外，它是算法的结果）。 

{ text: 'A', level: 0, children:  0 },    // A
{ text: 'B', level: 0, children:  1 },    // B
{ text: 'C', level: 1, children:  0 },    //   C
{ text: 'D', level: 0, children:  3 },    // D
{ text: 'E', level: 1, children:  2 },    //   E
{ text: 'F', level: 2, children:  0 },    //     F
{ text: 'F', level: 2, children:  0 },    //     G
{ text: 'H', level: 0, children: 18 },    // H
{ text: 'I', level: 1, children:  5 },    //   I
{ text: 'J', level: 2, children:  1 },    //     J
{ text: 'K', level: 3, children:  0 },    //       K
{ text: 'L', level: 2, children:  2 },    //     L
{ text: 'M', level: 3, children:  1 },    //       M
{ text: 'N', level: 4, children:  0 },    //         N
{ text: 'O', level: 1, children: 10 },    //   O
{ text: 'P', level: 2, children:  9 },    //     P
{ text: 'Q', level: 3, children:  7 },    //       Q
{ text: 'R', level: 4, children:  5 },    //         R
{ text: 'S', level: 5, children:  2 },    //           S
{ text: 'T', level: 6, children:  0 },    //             T
{ text: 'U', level: 6, children:  0 },    //             U
{ text: 'V', level: 5, children:  0 },    //           V
{ text: 'W', level: 5, children:  0 },    //           W
{ text: 'X', level: 4, children:  0 },    //         X
{ text: 'Y', level: 3, children:  0 },    //       Y
{ text: 'Z', level: 1, children:  0 },    //   Z

var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }],
    i = data.length,
    count = [];
	
while (i--) {
    if (data[i].level > 0) {
        count[data[i].level - 1] = (count[data[i].level - 1] || 0) + (count[data[i].level] || 0) + 1;
    }
    data[i].children = count[data[i].level] || 0;
    count[data[i].level] = 0;
}

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

带有预填充数组 count （不检查未定义）和级别变量的版本。 

var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }],
    i = data.length, l,
    count = Array.apply(null, { length: 50 }).map(function () { return 0; });
	
while (i--) {
    l = data[i].level;
    if (l) {
        count[l - 1] += count[l] + 1;
    }
    data[i].children = count[l];
    count[l] = 0;
}

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');
Nina Scholz
2016-02-10