ตรวจสอบว่าคีย์มีในทุกเซ็กเมนต์ขนาด K ของอาร์เรย์หรือไม่ใน C++

แนวคิด

กำหนดอาร์เรย์ arr[] ขนาด N, คีย์ X, และขนาดเซ็กเมนต์ K ต้องการตรวจสอบว่าคีย์ X ปรากฏในทุกเซ็กเมนต์ขนาด K ของอาร์เรย์หรือไม่

ตัวอย่าง: - arr = {4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4}, X=4, K=3 → Yes (4 เซ็กเมนต์: {4,6,3}, {5,10,4}, {2,8,4}, {12,13,4} ทุกเซ็กมี 4) - arr = {6, 9, 8, 13, 15, 4, 10}, X=9, K=2 → No

วิธีการแก้ปัญหา

วนลูปทุกเซ็กเมนต์ขนาด K (i = 0, K, 2K, ...) ค้นหา X ในเซ็กเมนต์นั้น หากไม่พบในเซ็กเมนต์ไหน → false ต้องจัดการเซ็กเมนต์สุดท้ายที่อาจมีขนาด < K ด้วย

ตัวอย่างโค้ด 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;
    }
    if (i == N) return true;
    int j;
    for (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;
}

ผลลัพธ์

Yes