이 문제에서 N개의 정수 값과 크기가 N인 창으로 구성된 배열 arr[]이 주어집니다. 우리의 임무는 크기가 k인 모든 창에서 첫 번째 음의 정수를 찾는 프로그램을 만드는 것입니다. . 존재하는 경우 첫 번째 음수를 인쇄합니다. 그렇지 않으면 음수가 존재하지 않음을 나타내는 0을 인쇄합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
Output: -2, -1, -1, 0, -6 설명 -
Size of window k = 2,
{-2, 2}, first negative is -2
{2, -1}, first negative is -1
{-1, 4}, first negative is -1
{4, 3}, first negative is 0 (no negative exists)
{3, -6}, first negative is -6 솔루션 접근 방식
문제를 해결하는 간단한 방법은 배열 arr[]를 탐색하여 크기가 k인 창을 만드는 것입니다. 그리고 각 창에서 첫 번째 음의 정수를 찾아 인쇄합니다.
솔루션은 작업을 수행하기 위해 두 개의 중첩 루프를 사용하는 순진한 솔루션입니다. 따라서 솔루션의 시간 복잡도는 O(n*k) 차수입니다.
예시
솔루션 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
void findFirstNegIntWindowK(int arr[], int n, int k){
bool negFound;
for (int i = 0; i<(n-k+1); i++)
{
negFound = false;
for (int j = 0; j<k; j++)
{
if (arr[i+j] < 0)
{
cout<<arr[i+j]<<"\t";
negFound = true;
break;
}
}
if (!negFound)
cout<<"0\t";
}
}
int main(){
int arr[] = {-2, 2, -1, 4, 3, -6};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"First negative integer in each with of size "<<k<<" is \n";
findFirstNegIntWindowK(arr, n, k);
return 0;
} 출력
First negative integer in each with of size 2 is -2 -1 -1 0 -6
문제를 해결하는 또 다른 방법은 슬라이딩 창과 유사한 개념을 사용하는 것입니다. . 이를 위해 우리는 dequeue를 생성할 것입니다. 크기가 k인 창의 모든 요소에 대해 크기가 k인 (양방향 대기열) 우리는 처음부터 배열을 순회하기 시작하고 크기 k의 큐에 있는 요소를 채울 것입니다. 그런 다음 배열의 각 요소에 대해 끝에서 한 요소를 제거하고 한 요소를 다른 요소에 추가합니다. 각 슬라이드 창에 대해 첫 번째 음수를 찾아 인쇄합니다. 음수를 찾기 위해 제거된 숫자가 창의 첫 번째 음수인지 여부를 확인하고, 그렇다면 첫 번째 음수에 대한 다음 요소를 확인하고 그렇지 않으면 그렇지 않습니다.
예시
솔루션 작동을 설명하는 프로그램
#include <bits/stdc++.h>
using namespace std;
void findFirstNegIntWindowK(int arr[], int n, int k){
deque<int> windowKsize;
int i = 0;
for (; i < k; i++)
if (arr[i] < 0)
windowKsize.push_back(i);
for (; i < n; i++){
if (!windowKsize.empty())
cout<<arr[windowKsize.front()]<<"\t";
else
cout<<"0\t";
while ( (!windowKsize.empty()) && windowKsize.front() < (i - k + 1))
windowKsize.pop_front();
if (arr[i] < 0)
windowKsize.push_back(i);
}
if (!windowKsize.empty())
cout<<arr[windowKsize.front()]<<" \t";
else
cout<<"0\t";
}
int main(){
int arr[] = {-2, 2, -1, 4, 3, -6};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"First negative integer in each with of size "<<k<<" is \n";
findFirstNegIntWindowK(arr, n, k);
return 0;
} 출력
First negative integer in each with of size 2 is -2 -1 -1 0 -6