Khái niệm
Đối với một mảng arr1 [] đã cho với kích thước của mảng N, một khóa khác X và một kích thước phân đoạn K, nhiệm vụ là xác định rằng khóa X có trong mọi phân đoạn có kích thước K trong arr1 [].
Đầu vào
arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4}
X = 4
K = 3 Đầu ra
Yes
Có sự tồn tại của 4 phân đoạn không chồng lên nhau có kích thước K trong mảng, {4, 6, 3}, {5, 10, 4}, {2, 8, 4} và {12, 13, 4}. 4 có mặt ở tất cả các phân đoạn.
Đầu vào
arr1[] = { 22, 24, 57, 66, 35, 55, 77, 33, 24, 46, 22, 24, 26}
X = 24
K = 5 Đầu ra
Yes
Đầu vào
arr1[] = { 6, 9, 8, 13, 15, 4, 10}
X = 9
K = 2 Đầu ra
No
Phương pháp
Trong trường hợp này, khái niệm rất đơn giản, chúng tôi xem xét mọi phân đoạn có kích thước K và xác minh xem X có xuất hiện trong cửa sổ hay không. Vì vậy, chúng tôi cần xử lý cẩn thận phân đoạn cuối cùng.
Ví dụ
Sau đây là việc thực hiện phương pháp trên -
// C++ code to determine the every segment size of
// array have a search key x
#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) {
// Search X in segment starting
// from index i.
int j;
for (j = 0; j < K; j++)
if (arr1[i + j] == X)
break;
// If loop didn't break
if (j == K)
return false;
}
// If N is a multiple of K
if (i == N)
return true;
// Check in last segment if N
// is not multiple of K.
int j;
for (j=i-K; j<N; j++)
if (arr1[j] == X)
break;
if (j == N)
return false;
return true;
}
// main driver
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