Kiểm tra khóa X có mặt trong mọi đoạn kích thước K của mảng (C++)

Khái niệm

Cho mảng arr[] kích thước N, khóa X và kích thước đoạn K. Xác định xem X có xuất hiện trong mọi đoạn không chồng chéo kích thước K của mảng hay không.

Ví dụ 1: arr[] = {4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4}, X = 4, K = 3 → Yes. Các đoạn: {4,6,3}, {5,10,4}, {2,8,4}, {12,13,4} — đều có 4.

Ví dụ 2: arr[] = {6, 9, 8, 13, 15, 4, 10}, X = 9, K = 2 → No.

Phương pháp

Duyệt mảng theo bước nhảy K. Với mỗi đoạn bắt đầu tại i, kiểm tra X có trong arr[i..i+K-1] không. Xử lý riêng đoạn cuối nếu N không chia hết cho K.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

bool findxinkindowSize1(int arr1[], int X, int K, int N){
    int i;
    for (i = 0; i < N; i = i + K) {
        int j;
        for (j = 0; j < K; j++)
            if (arr1[i + j] == X) break;
        if (j == K) return false; // Không tìm thấy X trong đoạn
    }
    if (i == N) return true; // N chia hết K
    // Kiểm tra đoạn cuối
    for (int j = i - K; j < N; j++)
        if (arr1[j] == X) break;
    if (j == N) return false;
    return true;
}

int main(){
    int arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 };
    int X = 4, K = 3;
    int N = sizeof(arr1) / sizeof(arr1[0]);
    if (findxinkindowSize1(arr1, X, K, N)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Đầu ra

Yes