[LeetCode][Hard] 128. Longest Consecutive Sequence

Leetcode 網址: https://leetcode.com/problems/longest-consecutive-sequence/

題目說明:

給定一個沒有排列的陣列，找出最長的連續序列長度。

Follow up: 你能否在 O(n) 時間內完成呢?

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(n) 時間，也就是說可以直接捨棄排序法了，

因為比較排序的排序法時間複雜度為 O( n log n) ~

所以很直覺出題者應該是想要我們使用額外的空間來處理問題。

所以我們直接把 nums 轉成 unordered_map，

以範例 1 而言就是 m[100] = 1, m[4] = 1, m[200] = 1, ..., m[2] = 1，

由於 unordered_map 訪問的平均時間為 O(1)，所以轉換過成只需要 O(n)，

接著直接對這些 map 中存在的元素做 traverse 紀錄長度，就可以找出答案了 ~

程式碼

class Solution {
public:
    int traverse(unordered_map<int, int>& m, int index, int offset, int value) {
        if (m.find(index + offset) != m.end()) {
            m[index + offset] = traverse(m, index + offset, offset, value + 1);
            return m[index + offset];
        }
        return value;
    }
    
    int longestConsecutive(vector<int>& nums) {
        int maxLength = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]] = 1;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i]] == 1) {
                m[nums[i]] = traverse(m, nums[i], -1, 1);
                m[nums[i]] = traverse(m, nums[i], 1, m[nums[i]]);
                maxLength = max(m[nums[i]], maxLength);
            }
        }
        return maxLength;
    }
};




結果

Runtime: 8 ms, faster than 98.60% of C++ online submissions for Longest Consecutive Sequence.

Memory Usage: 13.4 MB, less than 5.16% of C++ online submissions for Longest Consecutive Sequence.