ตรวจสอบ Key อยู่ในทุก Segment ขนาด K ใน Python

ภาพรวม

โจทย์ตรวจสอบว่าคีย์ p ปรากฏในทุก segment (ช่วง) ขนาด k ของอาร์เรย์หรือไม่

ตัวอย่าง

A = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]

p = 4, k = 3

Segments: [4,6,3], [5,10,4], [2,8,4], [12,13,4] → ทุก segment มี 4 → True

อัลกอริทึม

1. วนลูป segment เริ่มต้นที่ i=0, i+=k
2. ในแต่ละ segment หา p ถ้าไม่เจอ → False
3. ถ้า i == n (หารลงตัว) → True
4. ถ้าเหลือ segment สุดท้ายไม่ครบ k → เช็คส่วนที่เหลือ

โค้ด Python

def key_in_segment_k(arr, p, k, n):
    i = 0
    while i < n:
        j = 0
        while j < k:
            if i + j < n and arr[i + j] == p:
                break
            j += 1
        if j == k or i + j >= n:
            return False
        i += k
    if i == n:
        return True
    j = i - k
    while j < n:
        if arr[j] == p:
            break
        j += 1
    return j != n

arr = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
p, k = 4, 3
n = len(arr)
print(key_in_segment_k(arr, p, k, n))

วิธี Pythonic (Slicing)

def key_in_segments(arr, p, k):
    for i in range(0, len(arr), k):
        if p not in arr[i:i+k]:
            return False
    return True

ผลลัพธ์

True