Dãy liên tiếp dài nhất trong Python

Giả sử chúng ta có một mảng số nguyên. Chúng ta phải tìm độ dài của dãy các phần tử liên tiếp dài nhất. Ví dụ: [100, 4, 250, 1, 3, 2] -> kết quả 4 (dãy [1,2,3,4]).

Các bước giải quyết (O(n) time):

• Chuyển mảng thành set để tra cứu O(1)
• Duyệt từng phần tử i trong set: nếu i-1 không có trong set (tức i là đầu dãy)
• Từ i, đếm streak bằng cách tăng i liên tục khi i còn trong set
• Cập nhật longest = max(longest, streak)

Ví dụ

class Solution(object):
    def longestConsecutive(self, a):
        a = set(a)
        longest = 0
        for i in a:
            if i-1 not in a:
                current = i
                streak = 0
                while i in a:
                    i += 1
                    streak += 1
                longest = max(longest, streak)
        return longest

ob = Solution()
print(ob.longestConsecutive([100, 4, 250, 1, 3, 2]))

Đầu vào

[100, 4, 250, 1, 3, 2]

Đầu ra

4