LeetCode 128. Longest Consecutive Sequence [Hard] [C++] 解題筆記

 Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Follow up: Could you implement the O(n) solution? 

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

想法:

    這題主要有兩種解法，第一種是 O(nlogn)的方式，這種方式比較容易想到就是先將數列排序，然後只要依序遍歷並

檢查當前數列是否是連續的即可，排序可以先用 sort 來達成或是使用有序的容器(map, set)儲存都可。

第二種是 O(n) 的方式，這種方式就比較難想到了，O(n) 的方式又有兩種思路，第一種可以先將數列放入 unordered_set，

然後遍歷整個數列，如果當前數字是左邊界(沒有剛好比它小 1 的數字)就向右遍歷直到無法再找到連續的數字。

另一種方式我覺得比較難想到首先建立一個 unordered_map<int, int> 其中第二個數表示以第一個數做為邊界可以形成的最長

consecutive elements sequence，這邊的邊界可以是左邊界也可以是右邊界，之後遍歷整個數列，對每一個數 n 在 unordered_map 中找

n - 1 和 n + 1 的數，這邊分為四種情況:

1. n - 1 不存在 => n 為當前的左邊界

2. n + 1 不存在 => n 為當前的右邊界

3. n - 1 與 n + 1 皆不存在 => n 目前沒有其他相連的數字 => lce = 1

4. n - 1 與 n + 1 皆存在 => n 為兩個連續數列間的橋樑 => 兩個數列加上 n 會變更長的連續數列

之後只要依劇這4種情況將找到的左邊界與右邊界在 unordered_map 中的長度更新即可。

完整程式碼:

解法一(O(nlogn), sort by sorting):

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) { return 0; }
        sort(nums.begin(), nums.end());
        int length = 1;
        int max_length = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) { continue; }
            if (nums[i] != nums[i - 1] + 1) {
                max_length = max(length, max_length);
                length = 1;
            }   
            else {
                length++;
            }   
        }   
        max_length = max(length, max_length);
        return max_length;
    }   
};

解法二(O(nlogn), sort by set):

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) { return 0; }
        set<int> s(nums.begin(), nums.end());
        int max_length = 0;
        int length = 1;
        set<int>::iterator it = s.begin();
        it++;
        for (it; it != s.end();it++) {
            if (*it-- != *(it++) + 1) {
                max_length = max(length, max_length);
                length = 1;
            }
            else {
                length++;
            }
        }
        return max(length, max_length);
    }
};

解法三(O(n), unordered_set):

/* unordered_set, O(n) solution 
 * 每個數最多只會被訪問 2 次 => O(2n) => O(n)
 * */
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int max_length = 0;
        for (int n : nums) {
            // s is left boundary
            if (!s.count(n - 1)) {
                int length = 0;
                while (s.count(n++)) {
                    length++;
                }
                max_length = max(length, max_length);
            }
        }
        return max_length;
    }
};

解法四(O(n), unordered_map):

/* unordered_map O(n) solution
 * 不容易想，可多練習
 *
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // second 表示以 first 的數值作為邊界可以形成的最長 consecutive elements sequence 的長度
        unordered_map<int, int> m;
        int max_length = 0;
        
        for (auto n : nums) {
            // filter duplicate
            if (m.find(n) != m.end()) { continue; }
            auto it_l = m.find(n - 1);
            auto it_r = m.find(n + 1);
            // check if n is left boundary
            int l = it_l == m.end()? 0 : it_l->second;
            // check if n is right boundary
            int r = it_r == m.end()? 0 : it_r->second;
            // if n is left boundary: length = 0 + r + 1;
            // if n is right boundary: length = l + 0 + 1;
            // if n is middle number: length = l + r + 1;
            int length = l + r + 1;
            m[n] = m[n - l] = m[n + r] = length;
            max_length = max(max_length, length);
        }
        
        return max_length;
    }
};