java - 查找堆深度比 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 的回答，这里是伪代码。

• 为每个节点关联一个D字段，

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

• 从每个节点开始，沿着父链，直到到达一个非负 D 的节点，

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

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

链遍历在遇到第一个非负节点时停止，所有中间节点都变为非负。所以负节点只被访问一次，这证明了 O(n) 行为。

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

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

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