इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें N पूर्णांक मान और आकार N की एक विंडो शामिल है। हमारा कार्य आकार 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 [] आकार की खिड़कियों को बनाना। और प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक ढूंढ़कर प्रिंट करें।
समाधान एक भोला है जो ऑपरेशन करने के लिए दो नेस्टेड लूप का उपयोग करता है। इसलिए समाधान की समय जटिलता 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
समस्या को हल करने का एक अन्य तरीका स्लाइडिंग विंडो . जैसी अवधारणा का उपयोग करना है . इसके लिए, हम एक डिक्यू तैयार करेंगे (एक डबल-एंडेड कतार) आकार 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