โปรแกรมหาความยาวของลำดับตัวเลขเรียงติดกันมากที่สุดใน Python

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

ตัวอย่างเช่น หาก nums = [70, 7, 50, 4, 6, 5] ผลลัพธ์จะเป็น 4 เนื่องจากลำดับที่เรียงติดกันมากที่สุดคือ [4, 5, 6, 7] ความยาวคือ 4

ขั้นตอนการแก้ปัญหา (Hash Set - O(n))

1. แปลง nums เป็นเซตเพื่อกำจัดค่าซ้ำและค้นหา O(1)
2. กำหนด max_cnt = 0
3. สำหรับแต่ละ num ในเซต:
   • หาก num - 1 ไม่อยู่ในเซต (หมายถึง num เป็นจุดเริ่มต้นของลำดับ):
     • cnt = 0
     • วนลูป while num อยู่ในเซต:
       • num += 1
       • cnt += 1
     • max_cnt = max(max_cnt, cnt)
4. คืนค่า max_cnt

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

class Solution:
    def solve(self, nums):
        nums = set(nums)
        max_cnt = 0
        
        for num in nums:
            if num - 1 not in nums:
                cnt = 0
                while num in nums:
                    num += 1
                    cnt += 1
                max_cnt = max(max_cnt, cnt)
        
        return max_cnt

ob = Solution()
nums = [70, 7, 50, 4, 6, 5]
print(ob.solve(nums))  # Output: 4

อินพุต

[70, 7, 50, 4, 6, 5]

เอาต์พุต

4