Kiểm tra khóa có mặt trong mọi đoạn kích thước k của mảng trong Python

Cho mảng A kích thước N, giá trị p và kích thước đoạn k. Kiểm tra p có xuất hiện trong mọi đoạn liên tiếp độ dài k không.

Ví dụ: A=[4,6,3,5,10,4,2,8,4,12,13,4], p=4, k=3 → True.

Thuật toán

• Duyệt đoạn i từ 0 bước k:
  • Kiểm tra đoạn k phần tử có chứa p không
  • Nếu không → False
• Xử lý đoạn cuối dư (nếu N % k != 0)
• Trả về True nếu tất cả đoạn đều có p

Ví dụ mã Python

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

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

Đầu vào

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

Đầu ra

True