LeetCode圖解 | 128.最長連續序列
- 2020 年 2 月 24 日
- 筆記
下面開始今天的學習～
今天分享一個LeetCode題，題號是128，標題是最長連續序列，題目標籤是並查集和數組。
題目描述
給定一個未排序的整數數組，找出最長連續序列的長度。
要求算法的時間複雜度為 O(n)。
示例:
輸入: [100, 4, 200, 1, 3, 2] 輸出: 4 解釋: 最長連續序列是 [1, 2, 3, 4]。它的長度為 4。
解題
看評論和解題都沒有詳細介紹使用並查集去解這道題的，不過，話說並查集是哪種數據結構組成？
我也不知道並查集是哪一種數據結構，反正它就是一種數據結構。
我個人理解，並查集是兩個八竿子打不着關係的團體通過「邊」合併在一起，例如，兩個節點通過「邊」連在一起，兩棵樹通過「邊」形成一顆大樹，再例如，圖的兩個連通分量通過「橋」連在一起形成一個聯通分量。所以，我覺得並查集不是「結果」，而是有「過程」的數據結構。
好了，了解並查集，再看題目描述。
輸入數組[100, 4, 200, 1, 3, 2]，怎麼用並查集表示呢？
我們可以把數組裡的六個整數，看成六個獨立的團體，而且通過自環連接自己，如下圖：
獨立的集合
要注意，並查集是子節點是指向父節點的，所以，用數組（直接尋址表）表示並查集的時候，下標是子節點，下標所指的值是父節點；如果數據不是小整數或跨度比較大的時候，用散列表也可以表示並查集，鍵是子節點，值是父節點。
那怎麼進行「並」操作呢？
題目要求得到最長連續序列的長度，那就設定一個集合是連續序列的整數，「並」是將兩個集合之間合併在一起，就用「邊」連接起來。注意，一個集合可能是一個節點，也可能是已連續的多個節點。
如下圖，我用子節點小於父節點連接起來的，當然，你也可以用子節點大於父節點連接起來。
「並」操作
具體的程序代碼應該怎樣執行，看下面動畫就能看清楚什麼思路了，大家加油 8-)。
動畫：使用並查集
視頻大小：2.24M
Code：使用並查集
import java.util.HashMap; import java.util.Map; // 並查集 class Solution { public int longestConsecutive(int[] nums) { if (nums == null) return 0; if (nums.length <= 1) return nums.length; // 構建並查集 Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) if (!map.containsKey(num)) { map.put(num, num); // 並查集的狀態表達 if (map.containsKey(num - 1)) map.put(num - 1, num); if (map.containsKey(num + 1)) map.put(num, num + 1); } // 找到最長 int res = 1; for (int num : nums) { if (map.get(num) != num) { int len = parent(map, num) - num + 1; res = res > len ? res : len; } } return res; } private int parent(Map<Integer, Integer> map, int num) { if (map.get(num) == num) return num; return parent(map, map.get(num)); } }
如果為了提升時間上的效果，可以將未排序的整數數組進行升序，然後進行for循環遍歷，忽略相鄰兩個數相等的情況下，去統計連續序列的最長長度，找到最大值。
喜歡本文的朋友，關注「圖解面試算法」，收看有目共賞的算法動畫，一起領悟算法的魅力，大家加油 8-）
END
