Hello, I am Xiao Huang, a Java development engineer of Unicorn Enterprise. The school recruited dozens of offers, the annual salary is 20W~40W. Thank you for meeting us in the vast sea of people. As the saying goes: When your talent and ability are not enough to support your dream, please calm down and study. I hope you can study with me and work hard together to realize your own dream.

First, what is the parallel search set

The parallel lookup set is considered by many OIer to be one of the most concise and elegant data structures. It is mainly used to deal with the merging problem of disjoint sets and supports two operations:

  • Union: To combine two disjoint sets into a single set.
  • Find: Queries whether two elements are in the same collection.

Of course, this definition is confusing, so let’s do a sample analysis.

Two, in-depth understanding and look up sets

In the distant rivers and lakes, there is a group of martial arts people, they each fight for themselves, guarding their own guard the thing.

  • 1st: Good at sword and 98 power
  • Rank 2: Good at sword and 95 power
  • Rank 3: Good at stick. 93 power
  • 4th: Good at gun and 90 power

One day suddenly, an uninvited guest (small yellow) came to this all corners of the country, want to dominate all corners of the country, the battle of a bloody rain is about to pull open prelude.

  • Small yellow: good at machine gun, force value 100, treasure: and check collection

The situation of jianghu is divided by five people, as shown below:

  • The meaning of arrow: his eldest brother (for example, no. 2’s arrow points to him, so no. 2’s eldest brother is himself)

Huang saw the information of the other 4 people, using the treasure and check the collection to inquire about the relationship between No. 4 and the other several people, found that No. 4 is a lone person, decided to start with No. 4.

In a dark night, huang took a machine gun, the use of treasures and check the collection of the merger, the no. 4 to accept, become its younger brother.

No. 1, no. 2 and No. 3 heard that No. 4 was taken in last night and immediately held a meeting to discuss cooperation. No. 1 did not want to cooperate with the other two because of his height, so No. 2 and No. 3 had to cooperate.

Thus, the situation of rivers and lakes has changed again.Huang’s ambition can be hegemony of all corners of the country, then use treasures and check the collection respectively query 1, 2, 3 of the current state, that: 1 or a lone person, and 2, 3 has allied.

Huang again in a night of black wind high night and 1 battle night, the final use of treasures and check the collection of the merger, captured 1.

So far, there are only two factions in jianghu, no. 2 faction and small Yellow faction.

2 aware of the current yellow forces, take the initiative to banquet, hope that the river’s lake is not fighting, can be safe.

At the banquet, the number of faction 2 was smaller than that of the yellow faction, so faction 2 was officially swallowed by the yellow faction, and the rivers and lakes were officially unified.

Implement and search set

And check the initialization of the set:

class UnionAndFind(a){
    // Who is your eldest brother
    private int[] parent;
    // How many people are in your team
    private int[] size;
    // There are several factions
    int sets;

    / / initialization
    // Everyone's big brother is himself
    // Each team has 1 member
    public UnionAndFind(int N) {
        parent = new int[N];
        size = new int[N];
        help = new int[N];
        sets = N;
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1; }}}Copy the code

The time complexity here can be reduced to the O(1) level, if you don’t believe it, read on.

	// Check whether A and B are in the same camp
	public boolean isSameSet(int a, int b) {
        return find(a) == find(b);
    }
	// See who your ultimate brother is
    public int find(int i){
        while(i ! = parent[i]){ i = parent[i]; }return i;
    }                                                                                                                                                                                                                                                                                                                                                            
Copy the code

Then look up the Union method of the set: first find the final eldest brother of the two parameters, and the eldest brother with fewer brothers will follow the eldest brother with more brothers

	public void union(int a, int b) {
        int A = find(a);
        int B = find(b);
        if(A ! = B) {if (size[A] >= size[B]) {
                size[A] += size[B];
                parent[B] = A;
            } else{ size[B] += size[A]; parent[A] = B; } sets--; }}Copy the code

Four, real exercises

547. Number of provinces

  • Initialize the array, copy the above and look up the set
public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        UnionAndFind unionFind = new UnionAndFind(N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (isConnected[i][j] == 1&& i ! = j) { unionFind.union(i, j); }}}return unionFind.sets;
    }
Copy the code

5. Path compression optimization

Most of the problems have been solved with our current version of the pooled collection, but we can optimize the path compression for the current version of the pooled collection.

We can see that in our find() method, we will do a while() loop to find the eldest brother. This operation is a waste of time. Is there any way to optimize it?

As follows:We can see that for 6, 5, 3 and so on, every timefindWhen querying, it takes 2 or 3 times to find 1.

If we save the value and reattach it above 1 while doing the search, for example:

I’m going to look for 6, and I’m going to look for 5 and 3, so I’m going to save 6, 5, and 3 in a temporary array, and when I’m done, I’m going to hang those arrays directly below 1, so that the next time I do a query, I’m going to reduce the number of loops.

The find() operation becomes an O(1) level query time when the number of times we query is much greater than the amount of data we have.

public int find(int i) {
        int h = 0;
        while(i ! = parent[i]) { help[h++] = i; i = parent[i]; }for (h--; h >= 0; h--) {
            parent[help[h]] = i;
        }
        return i;
    }
Copy the code

Six, summarized

The search set algorithm is usually used to deal with some Disjoint Sets merging and query problems

Liguo also has a tag column for parallel search sets: parallel search sets

Just to give you a sense of the magic of path compression, you can reduce your time complexity down to O(1) by continuous path compression.

O(1) = O(1) = O(1) = O(1) = O(1) = O(1

For time complexity, any constant degree can be considered O(1) time complexity, and you can use HashMap to store it.

The content of this issue is over here, I am a Unicorn enterprise Java development engineer, you can leave a message or private message to add my wechat, we will see you next time!