Longest Consecutive Sequence ใน Python

กำหนดอาร์เรย์จำนวนเต็ม ต้องหาความยาวของลำดับตัวเลขที่เรียงติดกันมากที่สุด (ไม่จำเป็นต้องเรียงในอาร์เรย์)

ตัวอย่าง: [100, 4, 250, 1, 3, 2] → 4 เพราะลำดับ [1,2,3,4]

ขั้นตอนการแก้ปัญหา

• แปลงอาร์เรย์เป็น set เพื่อ O(1) lookup
• วนทุกตัว i ใน set: ถ้า i-1 ไม่อยู่ใน set (หมายถึง i เป็นจุดเริ่มต้นของลำดับ)
• นับ streak โดยเพิ่ม i ทีละ 1 จนกว่าจะไม่อยู่ใน set
• อัปเดต longest = max(longest, streak)

ตัวอย่างโค้ด

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]))

อินพุต

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

เอาต์พุต

4