Найти глубину кучи быстрее, чем 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 - позиция root.

Я также решил эту проблему с помощью рекурсии.Но тесты дают мне также «Превышен лимит времени».

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

Все, что нам нужно, это карта, которая указывает, где находятся дети, а затем выполните поиск в ширину.Как мы можем видеть в выходных данных ниже, сложность O (n).

function f(A){
  let map = {};
  
  A.map((parentIdx, childIdx) => {
    if (map[parentIdx])
      map[parentIdx].push(childIdx);
    else
      map[parentIdx] = [childIdx];
  });
  
  let maxDepth = 0;
  let queue = [[-1, 0]];
  
  while (queue.length){
    const [node, depth] = queue.shift();

    console.log(
      `node: ${node}, children: [${map[node] || ''}], ` +
      `current depth: ${depth}`);

    maxDepth = Math.max(maxDepth, depth);
    
    if (map[node])
      for (let child of map[node])
        queue.push([child, depth + 1]);
  }
  
  return maxDepth;
}

var arr = [4, -1, 4, 1, 1];
console.log(f(arr));

Answer 2

Запомните глубину посещенных узлов в массиве.Начните переход от первого входного элемента к его корню и на глубине хранилища возврата к массиву посещенных узлов.При каждом переходе от дочернего элемента к родительскому элементу проверяйте, рассчитана ли уже глубина.Если да, вам не нужно идти по этому маршруту во второй раз, и вы можете напрямую использовать предварительно рассчитанное значение.Будет на).

Answer 3

Чтобы обосновать ответ Матея, вот псевдокод.

• свяжите поле D с каждым узлом,

• инициализируйте все D к -1,

• от каждого узла, следуйте по родительской цепочке, пока не достигнете узла с неотрицательным D,

• , если достигнут корень,установите его D в 0,

• , отслеживая цепь в обратном направлении, обновляйте все больше D.

Обход цепи останавливается на первом неотрицательномузел встретился, и все промежуточные узлы стали неотрицательными.Таким образом, отрицательные узлы посещаются только один раз, и это оправдывает поведение O (n).

Обновление всех узлов в цепочке имеет решающее значение, в противном случае одни и те же узлы можно посещать несколько раз.В худшем случае это может привести к операциям O (n²).

Стоит отметить, что алгоритму требуется стек, чтобы сделать возможным обратный переход.В худшем случае глубина стека может достигать n, добавляя дополнительное пространство для хранения O (n) (или риск переполнения стека не принимается во внимание).

Лучшим вариантом может быть использование Dполе пройденных узлов для хранения «индекса возврата» и формирования временной обратной цепочки.

Answer 4

Хотя вы можете найти максимальную глубину в O (n), основываясь на вашем массиве родителей, как описано Matej, возможно, стоит преобразовать этот массив в древовидную структуру, более удобную для навигации в направлении от родителя к ребенкуузел.Вы уже делаете это с вашим классом Node, но ваш метод fillChildren имеет сложность O (n²), так как вам приходится сканировать весь массив снова и снова, чтобы найти дочерние элементы текущего узла.

Вместо этогоВы можете создать Map<Integer, Set<Integer>>, сопоставляя узлы их дочерним узлам.Таким образом, вы можете создать все дерево в одном цикле над массивом в O (n).

static Map<Integer, Set<Integer>> makeTree(int[] parents) {
    Map<Integer, Set<Integer>> tree = new HashMap<>();
    for (int i = 0; i < parents.length; i++) {
        tree.computeIfAbsent(parents[i], x -> new HashSet<>()).add(i);
    }
    return tree;
}

Затем вы можете легко написать рекурсивную функцию для получения максимальной глубины дерева:

static int depth(Map<Integer, Set<Integer>> tree, int node) {
    return tree.containsKey(node) 
            ? 1 + tree.get(node).stream().mapToInt(n -> depth(tree, n)).max().getAsInt()
            : 0;
}

Сложность для обоих шагов равна O (n), если массив представляет собой дерево, поскольку каждый узел посещается ровно один раз.Если массив может также показать ориентированный граф, вы должны отслеживать уже посещенные ранее узлы.Для вашего примера используйте его так:

int[] array = {4, -1, 4, 1, 1};
Map<Integer, Set<Integer>> tree = makeTree(array);
System.out.println(depth(tree, -1)); // 3

---

Как и в любом рекурсивном алгоритме, он может достичь максимальной глубины рекурсии, если дерево очень и очень глубокое.Он может быть переписан итеративным способом с использованием Stack, но не будет таким кратким.

Stack<Integer> stack = new Stack<>();
stack.add(-1);
int[] depth = new int[array.length];
while (! stack.isEmpty()) {
    int node = stack.pop();
    for (Integer child : tree.getOrDefault(node, Collections.emptySet())) {
        depth[child] = node == -1 ? 1 : depth[node] + 1;
        stack.add(child);
    }
}
System.out.println(IntStream.of(depth).max().getAsInt());