Python: หาช่วงติดต่อกันของค่า K ที่ยาวอย่างน้อย N ตัว

บทนำ

โจทย์: ในลิสต์ หาช่วงติดต่อกัน (consecutive range) ที่มีค่าเท่ากับ K และมีความยาวมากกว่าหรือเท่ากับ N คืนค่าเป็น tuple (start_index, end_index)

อัลกอริทึม: Single Pass with State Tracking

ใช้ตัวแปรติดตามสถานะ: previous, beg (เริ่มต้น), end (สิ้นสุด)

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

def find_consecutive_ranges(lst, k, n):
    """หาช่วงติดต่อกันของค่า k ที่มีความยาว >= n"""
    result = []
    beg = end = 0
    previous = None  # ใช้ None แทนค่าเริ่มต้นที่อาจชนกับข้อมูล
    
    for index, element in enumerate(lst):
        if element == k:
            end = index
            if previous != k:
                # เริ่มกลุ่มใหม่
                beg = index
        else:
            # จบกลุ่ม - ตรวจสอบความยาว
            if previous == k and (end - beg + 1) >= n:
                result.append((beg, end))
        previous = element
    
    # ตรวจสอบกลุ่มสุดท้าย (ถ้าลิสต์จบด้วยค่า k)
    if previous == k and (end - beg + 1) >= n:
        result.append((beg, end))
    
    return result

# ทดสอบ
my_list = [3, 65, 33, 23, 65, 65, 65, 65, 65, 65, 65, 3, 65]
K = 65
N = 3

print(f"ลิสต์: {my_list}")
print(f"K = {K}, N = {N}")

ranges = find_consecutive_ranges(my_list, K, N)
print(f"ช่วงที่พบ: {ranges}")

ผลลัพธ์

ลิสต์: [3, 65, 33, 23, 65, 65, 65, 65, 65, 65, 65, 3, 65]
K = 65, N = 3
ช่วงที่พบ: [(4, 10)]

คำอธิบาย

• Index 1: 65 (ความยาว 1) - ไม่ผ่าน N=3
• Index 4-10: 65 ติดต่อกัน 7 ตัว - ผ่าน N=3 → (4, 10)
• Index 12: 65 (ความยาว 1) - ไม่ผ่าน

เวอร์ชันสั้นด้วย itertools.groupby

from itertools import groupby

def find_ranges_groupby(lst, k, n):
    result = []
    for key, group in groupby(enumerate(lst), key=lambda x: x[1] == k):
        if key:  # เป็นกลุ่มของค่า k
            group_list = list(group)
            if len(group_list) >= n:
                start = group_list[0][0]
                end = group_list[-1][0]
                result.append((start, end))
    return result

print(find_ranges_groupby(my_list, K, N))  # [(4, 10)]

กรณีใช้งานจริง

• ตรวจจับสัญญาณต่อเนื่องใน time series (เช่น อุณหภูมิสูงกว่าเกณฑ์)
• หาลำดับชัยชนะติดต่อกันในกีฬา
• วิเคราะห์ log: error ติดต่อกันมากกว่า N ครั้ง

ข้อควรระวัง

• โค้ดต้นฉบับใช้ previous = 1 ซึ่งอาจชนกับข้อมูลจริง → ควรใช้ None
• ต้องตรวจสอบกลุ่มสุดท้ายหลังจบลูป (edge case)
• groupby ต้องการข้อมูลที่ "ติดต่อกัน" แล้ว - ไม่ต้อง sort

สรุป

อัลกอริทึม single pass O(n) ใช้หน่วยความจำ O(1) (ไม่นับผลลัพธ์) เหมาะสำหรับข้อมูลขนาดใหญ่ วิธี groupby อ่านง่ายกว่าแต่ใช้หน่วยความจำเพิ่ม