128. Longest Consecutive Sequence

128. Longest Consecutive Sequence

這一題的題目敘述寫的沒有非常清楚，在面試的時候要問清楚。沒寫清楚的地方是題目說了這是一個沒有排序過的陣列，但是實際上要找的字序列，並不是要按照原本題目的順序的。

例如題目中給的例子：

nums = [100,4,200,1,3,2]

如果要抱持原先的順序，那只有一個子序列是 [1, 2] ，但是題目期待的答案是 [1, 2, 3, 4] 這個子序列。如果說要暴力解，最直覺的少說也一定要兩個 for 迴圈，時間複雜度絕對大於 $O(N^2)$（實際上是$O(N^3)$）。

排序

但是這題可以很快速的簡化，那就是如果先做了排序，時間複雜度就可以直接降低成 $O(N log N)$ ，因為排序過後的陣列，就可以直接找出是不是連續子序列，其中陣列裡面有可能會有重複的值，但是重複的值是沒辦法放入子序列的，可以一開始就用把所有重複的值給去掉。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        nums = list(set(nums))
        nums.sort()
        ans = 1
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]+1:
                count += 1
            else:
                ans = max(ans, count)
                count = 1
        return max(ans, count)

Heap

上面的做法有在官方裡面，我當時想到的方法是另外一個，其實時間複雜度也是一樣，原理也和上面的作法一樣，只是我的排序的方法是透過將元素加入到 heap 裡面，接著再一個一個把最小值 pop 出來，如果前一個最小值比我的當前值小於一，那我就繼續累加，如果不是差一，重新設定計數器。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        q = []

        nums = set(nums)
        for num in nums:
            heapq.heappush(q, num)
        first = heapq.heappop(q)
        most = 1
        count = 1
        while q:
            tmp = heapq.heappop(q)
            if tmp == (first + 1):
                count += 1
            else:
                count = 1
            most = max(most, count)
            first = tmp
        return most