Расширенная структура данных - UnionFind. Найдите старшего брата.

Расширенная структура данных - UnionFind. Найдите старшего брата.

Итак, вы решили сделать еще один шаг, а? Вместо того, чтобы рассчитываться с помощью Array и, возможно, LinkedList.

Хотя нет ничего плохого в том, чтобы просто знать основные из них, вы все равно можете быть надежным разработчиком.

Но если вы когда-нибудь захотите стать инженером, давайте рассмотрим:

Шаг 0. Почему? (Если вы профессионал, перейдите к шагу 1)

Что такое UnionFind и зачем он нам нужен?

Помните Audible и Amazon, а?

Теперь кто в доме хозяин?

Да! Audible принадлежит Amazon.

Хорошо, это звучит слишком просто, мы можем просто получить HashMap и просто указать Audible на его родительский элемент.

Хорошо, хорошо, представьте, что вы занимаетесь разработкой системы и вам нужно указать тысячам сотрудников на их родителей, а?

Да, и усложняем задачу, допустим, компании все время сливаются и продают.

Здорово! Вы согласились, что нам нужно что-то эффективное и профессиональное.

Шаг 1. Как?

Итак, для профессионалов я прямо говорю вам, что UnionFind на самом деле является деревом.

Вы были правы, использование HashMap или Array сделало бы эту работу, но нам нужно немного тонкого сжатия пути, и поверьте мне, эта структура данных полна ловушек, которые вы можете легко заполнить ошибками, если неосторожно или даже просто устали.

Для краткости мы используем простой примитивный массив Java. (Вы можете легко заменить его на HashMap).

• 1.1. Конструктор

Мы просто указываем каждому на себя. Это означает, что все - разрозненная точка. Audible принадлежит Audible, что означает, что его еще не приобрела какая-либо другая компания.

public ConnectingGraph_589(int n) {
    // do intialization if necessary
    father = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

• 1.2. Соединять

Соедините две компании вместе. например указывая на Audible как на сына Амазонки. Это означает, что Amazon приобретает Audible.

public void connect(int a, int b) {
    // write your code here
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        father[rootA] = rootB;
    }
}

• 1.3. Запрос

Проверьте, принадлежат ли две компании к одной корпорации.

Это означает возврат true, если Audible и Amazon имеют одного и того же БОЛЬШОГО брата - Amazon.

Или, допустим, вернусь, если у Nokia и Microsoft есть один и тот же БОЛЬШОЙ брат - MS.

public boolean query(int a, int b) {
    // write your code here
    return find(a) == find(b);
}

• 1.4 Найти

Это лучшая часть структуры данных, поскольку вы рекурсивно находите БОЛЬШОГО брата и тем временем обновляете всех дочерних элементов.

private int find(int x) {
    if (father[x] == x) {
        return x;
    } else {
        return father[x] = find(father[x]);
    }
}

Последний шаг, покажите код:

public class ConnectingGraph_589 {
    private int[] father;

    /*
     * @param n: An integer
     */
    public ConnectingGraph_589(int n) {
        // do intialization if necessary
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    public void connect(int a, int b) {
        // write your code here
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: A boolean
     */
    public boolean query(int a, int b) {
        // write your code here
        return find(a) == find(b);
    }

    private int find(int x) {
        if (father[x] == x) {
            return x;
        } else {
            return father[x] = find(father[x]);
        }
    }
}

Чтобы узнать больше об алгоритмах, посетите мой Github https://github.com/oliverwreath/JiuZhang.git

Итак, готово, давайте сделаем это как следует и настроим на успех!

Не стесняйтесь ставить лайки, делиться, комментировать ниже, чтобы поделиться своими мыслями о плюсах и минусах этого быстрого подхода.