查找堆深度比O(n ^ 2)快

Question

帮我优化算法.我在数组中有一堆.数组中的每个数字表示父项.根是-1.我需要找到堆的深度.例:

数组是4 -1 4 1 1

答案是3.

这是我的代码

static int findMax(int[] mas) {
    int a[] = new int[mas.length];
    a[pos] = 1;
    int max = 0;

    for (int j = 0; j < mas.length; j++) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0 && a[mas[i]] != 0) {
                a[i] = a[mas[i]] + 1;
                if (a[i] > max)
                    max = a[i];
            }
        }
    }
    return max;
}

pos位置 - 根位置.

我也用递归解决了这个问题.但测试也给了我"超出时间限制".

static class Node {
        static int nodesCount = 0;

        int val;
        int deep;
        List<Node> childrens = new ArrayList<>();
        static Set<Integer> deeps = new HashSet<>();

        public Node(int val, int deep) {
            this.val = val;
            this.deep = deep;
            deeps.add(deep);
            nodesCount++;
        }

        public List<Node> getChildrens() {
            return childrens;
        }

        public int getDeep() {
            return deep;
        }
    }
static int findMax(int [] mas){
    Node head = null;
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == -1)
            head = new Node(i, 1);
    }
    fillChildren(head, mas);
    return Node.deeps.stream().max(Comparator.naturalOrder()).get();
}

private static void fillChildren(Node head, int[] mas) {
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == head.val) {
            Node child = new Node(i, head.getDeep() + 1);
            head.getChildrens().add(child);
            fillChildren(child, mas);
        }
    }
}

Answer 1

为了证实 Matej 的答案，这里是伪代码。

\n\n

\n

• 将 D 字段关联到每个节点，

\n

• 将所有 D 初始化为 -1，

\n

• 从每个节点，沿着父链，直到到达具有非负 D 的节点，

\n

• 如果到达根，则将其 D 设置为 0，

\n

• 向后追踪链条，不断更新D。

\n

\n\n

链遍历在遇到的第一个非负节点处停止，并且所有中间节点都变为非负节点。因此负节点仅被访问一次，这证明了 O(n) 行为的合理性。

\n\n

更新链中的所有节点至关重要，否则相同的节点可能会被多次访问。在最坏的情况下，这可能会导致 O(n\xc2\xb2) 次操作。

\n\n

值得注意的是，该算法需要一个堆栈来使向后遍历成为可能。最坏的情况下，栈深度可以达到n，增加额外的O(n)存储空间（或者不考虑栈溢出的风险）。

\n\n

更好的选择可能是使用遍历节点的D字段来存储“返回索引”并形成临时的反向链。

\n