C++ में आकार K की प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक खोजना

समस्या विवरण

इस समस्या में, हमें N पूर्णांक मानों वाली एक सरणी arr[] और आकार K की एक विंडो दी गई है। हमारा कार्य आकार K की प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक खोजने के लिए एक प्रोग्राम बनाना है। यदि ऋणात्मक संख्या मौजूद है तो हम पहले ऋणात्मक संख्या को प्रिंट करेंगे अन्यथा 0 प्रिंट करेंगे, जो दर्शाता है कि कोई ऋणात्मक मौजूद नहीं है।

उदाहरण

इनपुट: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
आउटपुट: -2, -1, -1, 0, -6

व्याख्या

विंडो आकार k = 2:
{-2, 2}, पहला ऋणात्मक -2
{2, -1}, पहला ऋणात्मक -1
{-1, 4}, पहला ऋणात्मक -1
{4, 3}, पहला ऋणात्मक 0 (कोई ऋणात्मक नहीं)
{3, -6}, पहला ऋणात्मक -6

हल का दृष्टिकोण

विधि 1: नेस्टेड लूप (O(N×K)) - भोला

समस्या को हल करने का एक सरल तरीका सरणी arr[] को पार करके आकार 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 << "आकार " << k << " की प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक है:\n";
    findFirstNegIntWindowK(arr, n, k);
    return 0;
}

विधि 2: स्लाइडिंग विंडो के साथ डीक्यू (O(N)) - इष्टतम

समस्या को हल करने का एक अन्य तरीका स्लाइडिंग विंडो अवधारणा का उपयोग करना है। इसके लिए, हम वर्तमान विंडो के सभी ऋणात्मक तत्वों के इंडेक्स को संग्रहीत करने के लिए आकार K का एक डीक्यू (डबल-एंडेड क्यू) बनाएंगे। हम सरणी की शुरुआत से पार करना शुरू करेंगे और आकार K के डीक्यू में तत्व भरेंगे। और फिर, सरणी के प्रत्येक तत्व के लिए, हम एक छोर से एक तत्व हटाएंगे और दूसरे में जोड़ेंगे। प्रत्येक स्लाइड की गई विंडो के लिए हम पहला ऋणात्मक संख्या खोजेंगे और प्रिंट करेंगे।

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

void findFirstNegIntWindowK(int arr[], int n, int k) {
    deque<int> dq; // ऋणात्मक तत्वों के इंडेक्स संग्रहीत करता है
    
    // पहली विंडो प्रोसेस करें
    for (int i = 0; i < k; i++) {
        if (arr[i] < 0)
            dq.push_back(i);
    }
    
    // शेष विंडो प्रोसेस करें
    for (int i = k; i < n; i++) {
        // पिछली विंडो का उत्तर प्रिंट करें
        if (!dq.empty())
            cout << arr[dq.front()] << "\t";
        else
            cout << "0\t";
        
        // विंडो से बाहर के इंडेक्स हटाएं
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();
        
        // वर्तमान तत्व जोड़ें यदि ऋणात्मक है
        if (arr[i] < 0)
            dq.push_back(i);
    }
    
    // अंतिम विंडो प्रिंट करें
    if (!dq.empty())
        cout << arr[dq.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 << "आकार " << k << " की प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक है:\n";
    findFirstNegIntWindowK(arr, n, k);
    return 0;
}

आउटपुट

आकार 2 की प्रत्येक विंडो में पहला ऋणात्मक पूर्णांक है:
-2  -1  -1  0  -6

जटिलता विश्लेषण