LeetCode Union-Find(並查集)特集(二)

LeetCode Union-Find(並查集)特集(二)
Union-Findの適用状況を確認します
セットの使用と確認方法
セットを並べて調べる機能から、明らかにテーマには「クエリー」が必要で、「マージ」操作で使用することが考えられます.ポイントは合併です.(クエリー用mapのみを考慮すればよい)、このマージはマージパスを記録する必要がないことに注意してください.(これは,経路圧縮により既存の経路が破壊され,既存のツリー構造が破壊されるためである)
私がやった問題から見ると、セットの使用は明らかな特徴を持っています.一つはBFSやDFSとよく似ていることです.すなわちBFSまたはDFSで解決できるように見える.二つ目はデータ分類の特性を持つことである.ここの分類は抽象的だ.いくつかの問題では、ベクトルまたは関係行列に対する関係が直接与えられる可能性があります.いくつかの問題では、あいまいな問題があります.たとえば、隣接する数値が同類であることを条件として、後述する区間のマージ(セグメントマージ)について説明します.
セットのメリットを確認
確かにBFS+DFSで解決できる問題はたくさんあります.しかし、BFSやDFSの利用ができない、あるいは不便であるという問題がある.次に例を挙げます.
ProblemA:n*nのサイズの関係行列を与え、マージ後の連通ブロック数を出力することを要求する.
上記の問題に対してDFSとBFSは完全に適任である.複雑度はO(N 2)であるが,逆に用いて集計することはうまくいかない.その後の詳細な複雑度解析から,良く最適化されていない限りO(1)複雑度に達するユニオン操作は,使用して調査しても現実的ではないことが分かった.
次に、
ProblemB:nの大きさの関係対ベクトルを与え、結合後の連通ブロック数を出力することを要求する.
この問題は上の問題と比較して、情報の出し方が違うだけです.しかし、この方法は、冗長情報(すなわち、リレーショナルマトリクスの0)を回避する.この場合、DFS、BFS、並列調査セットの複雑度はいずれも低下し、そのうちDFS、BFSの複雑度はO(N)であり、調査セットは前述したように、複雑度は近似O(N)に達するしかない.
次に、
ProblemC:nのサイズの操作シーケンスが与えられ、操作ごとに2つの形式がある可能性があります.以下の通りです.1.[0, i, j] -> i, j 2.[1, k]-> k 。クエリー操作の結果からなる結果ベクトルを出力する必要があります.
これでどうですか.DFS,BFSは記憶化を用いても複雑度O(kここで,BFSとDFSはいずれも最後の結果のみを返すが,関係全体の内容は何も保存されていないためである.
セットを再考して調べると,現在の構造に対して1つの記録があるため,既存に保存されている構造にもう1つの関係の情報を加えるだけでよい.そして記憶化を採用すれば,O(N)の複雑さでこの問題を解決できる.
個人的にはこのようなダイナミックなクエリーこそ、検索セットの真髄だと感じています.のしかし、しばらく対応する例題が見つからず、見つけてから戻ってきて補充した.
次に、区間の併用例を説明します.
区間の並列調査セットの適用例--LeetCode 128.Longest Consecutive Sequence
タイトルの説明
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2] , The longest consecutive elements sequence is [1, 2, 3, 4] . Return its length: 4 .
Your algorithm should run in O(n) complexity.
構想分析
問題は複雑さの要求はO(N)であることを硬く教えてくれた.直接分析する必要はありません.
ここでのマージ情報の暗黙的:相関条件は2つの数が隣接している.具体的な実装はともかく,各単点が徐々に結合するにつれて線分となり,線分間の結合が主な問題となることが考えられる.ここで問題の性質を調べ集めると現れた.
既存の条件について直接作成してセットを調べることも可能です.しかし、もっと考えてみると、私たちはそんなに多くしなくてもいいことに気づきました.もし私たちが人為的に規定して集中したら、根の位置を調べます.
例えば、固定ルートは区間の左端に位置し、現在合併が必要な数i、右側i + 1はルートノードである場合を考慮する.では、father[i + 1] = father[i]だけでいいです.ここでは1歩Find()操作の時間を省いた.
また、この位置のFind()関数の使用を省くため、Union()全体のうち1箇所だけがFind()を必要とする.したがって、Union()関数にFind()関数のコードを直接埋め込むことができる.
さらに考えてみると、Union Find全体に1つの関数しかないので、この構造は実際に構築する必要はありません.のしかし、書くことで考えがより明確になることを考えると(最も重要なのは書く前にそんなに考えられるはずがない)、コードに書いてしまいました.
コード実装

//BLOG VERSION

struct UF{
    UF() {
        maximum = 0;
    }
    void Union(int i) {
        if (range[i].size() > 0) return ; // has occured.
        range[i] = vector<int>({i, i});
        father[i] = i;       
        //update range only at root point.
        // let root always at the mostleft in the range. 
        int t = i;
        if (range[i - 1].size() > 0) {
            t = i - 1;
            while (father[t] != t) t = father[t]; // t is the root for i - 1

            if (range[t][1] == i - 1) {
                //can merge.
                range[t][1] = i; father[i] = t;
                //comdense the path.
                int j = i - 1;
                while (j != father[j]) {
                    int temp = father[j];
                    father[j] = t;
                    j = father[j];
                }
            }
        }

        if (range[i + 1].size() > 0) {
            //this condition is enough.
            range[t][1] = range[i + 1][1]; father[i + 1] = t; // since no more info. can not comdence some path now.
        }
        if (range[t][1] - range[t][0] > maximum) maximum = range[t][1] - range[t][0];
    }
    unordered_map<int, vector<int>> range;// record the range.
    unordered_map<int ,int> father; //recored the uf struct.
    int maximum;
};
class Solution {
public:  
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        UF uf_set;
        for (int i = 0; i < nums.size(); ++i) {
            uf_set.Union(nums[i]);
        }
        return uf_set.maximum + 1;
    }
};

その他の詳細
この問題を使って調べ集めるのは自然にいい方法だが、実は別の選択肢もある.重要な点は、この問題の合併は区間の端点でしか行われないことです.したがって、1つのセグメントには、その端点に記録して長さを記録するだけで、マージされたセグメントの現在の情報を記述することができます.
このような考え方の方法をお勧めします.https://discuss.leetcode.com/topic/5333/possibly-shortest-cpp-solution-only-6-lines/10 やり方は非常に簡潔だ.
The End.