के आकाराच्या प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक


अडचण पातळी मध्यम
वारंवार विचारले एकत्रित ऍमेझॉन पोपल सोरोको
अरे रांग सरकता विंडो

समस्या विधान

"आकार के प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक" ही समस्या आपल्याला असे सूचित करते की अॅरे सकारात्मक आणि नकारात्मक पूर्णांक असलेले, आकाराच्या प्रत्येक विंडोसाठी त्या विंडोमध्ये प्रथम नकारात्मक पूर्णांक मुद्रित करते. कोणत्याही विंडोमध्ये नकारात्मक पूर्णांक नसेल तर आउटपुट 0 (शून्य).

उदाहरणे

arr[] = {5, -2, 3, 4, -5}
k = 2
-2 -2 0 -5

 

के आकाराच्या प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक

arr[] = {7, 9, -1, 2, 3, 4, -2, -3, -4}
k = 3
-1 -1 -1 0 -2 -2 -2

भोळे दृष्टिकोन

आकार के प्रत्येक विंडोसाठी, विंडोच्या सर्व घटकांमधून जा आणि प्रथम नकारात्मक पूर्णांक मुद्रित करा.

  1. मी 0 ते (एन - के) च्या बरोबरीसाठी एक लूप चालवा, येथे प्रत्येक मी के के आकाराच्या विंडोशी संबंधित आहे.
  2. J साठी समान नेस्ड लूप चालवा i ते (i + के) (समाविष्ट नाही). ही पळवाट i खिडकीवरुन फिरते.
  3. अररचे मूल्य [जे] नकारात्मक असल्यास ते मुद्रित करा आणि खंडित करा, अन्यथा पुढील घटकाची तपासणी करणे सुरू ठेवा.
  4. विंडोमध्ये नकारात्मक घटक नसल्यास 0 प्रिंट करा.

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी = ओ (एन * के)
स्पेस कॉम्प्लेक्सिटी = ओ (1)
जेथे n दिलेलेल्या अ‍ॅरे मधील घटकांची संख्या आहे.

आम्ही आकार के प्रत्येक विंडोसाठी स्वतंत्रपणे समस्या सोडवत असल्याने आम्ही सर्वसाधारणपणे एन * के घटकांद्वारे जात आहोत. आणि अशा प्रकारे बहुपदीय काळातील गुंतागुंत. आणि आम्ही काहीही साठवले नाही म्हणून जागेची जटिलता स्थिर आहे.

आकार के प्रत्येक विंडोमध्ये प्रथम प्रथम नकारात्मक पूर्णांक शोधण्यासाठी जावा कोड

class FirstNegativeIntegerInEveryWindowOfSizeK {
    private static void firstNegativeInteger(int[] arr, int k) {
        int n = arr.length;

        // Run a loop corresponding to every window in the array
        for (int i = 0; i <= n - k; i++) {
            boolean negFound = false;
            // Traverse the window
            for (int j = i; j < i + k; j++) {
                // If current element if negative print it
                if (arr[j] < 0) {
                    System.out.print(arr[j] + " ");
                    negFound = true;
                    break;
                }
            }

            // if there is no negative element then print 0
            if (!negFound)
                System.out.print("0 ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, -2, 3, 4, -5};
        int k1 = 2;
        firstNegativeInteger(arr1, k1);

        // Example 2
        int arr2[] = new int[]{7, 9, -1, 2, 3, 4, -2, -3, -4};
        int k2 = 3;
        firstNegativeInteger(arr2, k2);
    }
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

आकाराच्या प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक शोधण्यासाठी सी ++ कोड

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

void firstNegativeInteger(int *arr, int k, int n) {
    // Run a loop corresponding to every window in the array
    for (int i = 0; i <= n - k; i++) {
        bool negFound = false;
        // Traverse the window
        for (int j = i; j < i + k; j++) {
            // If current element if negative print it
            if (arr[j] < 0) {
                cout<<arr[j]<<" ";
                negFound = true;
                break;
            }
        }
        
        // if there is no negative element then print 0
        if (!negFound)
            cout<<"0 ";
    }
    
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {5, -2, 3, 4, -5};
    int k1 = 2;
    firstNegativeInteger(arr1, k1, sizeof(arr1) / sizeof(arr1[0]));

    // Example 2
    int arr2[] = {7, 9, -1, 2, 3, 4, -2, -3, -4};
    int k2 = 3;
    firstNegativeInteger(arr2, k2, sizeof(arr2) / sizeof(arr2[0]));
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

इष्टतम दृष्टीकोन

वरील समस्येचे निराकरण करण्याचा इष्टतम दृष्टीकोन म्हणजे डेक आणि स्लाइडिंग विंडो तंत्र वापरणे. Deque विंडोमध्ये नकारात्मक घटकांची अनुक्रमणिका संग्रहित करते. डेकचा पहिला घटक विंडोमधील पहिल्या नकारात्मक घटकाच्या अनुक्रमणिकेशी संबंधित आहे. विंडो बदलताना डेक मधून मागील विंडो एलिमेंट काढून टाका आणि नवीन एलिमेंट ड्यूकमध्ये जोडा. जर प्रथम नकारात्मक घटकाची तपासणी करताना Deque रिक्त असेल तर 0 मुद्रित करा.

  1. तयार Deque प्रश्न के आकाराच्या पहिल्या विंडोचा विचार करा.
  2. पहिल्या घटकांचा आढावा घ्या विंडोजर घटक नकारात्मक असेल तर त्याची अनुक्रमणिका डेकच्या शेवटी दाबा.
  3. ट्रॅव्हर्सलच्या शेवटी, जर ड्यूक रिक्त प्रिंट 0 असेल तर, अन्यथा डेकमधील प्रथम घटक पहिल्या नकारात्मक घटकाच्या अनुक्रमणिकेशी संबंधित असेल.
  4. उर्वरित अ‍ॅरेमध्ये आक्रमक करा (इंडेक्स के ते एन - 1 पर्यंत प्रारंभ करा), तर डेकचा पुढचा भाग (आय-के) कमी करण्यापेक्षा कमी आहे. जर सद्य घटक नकारात्मक असेल तर ते डेकमध्ये जोडा.
  5. डेकमधील पहिला घटक या विंडोच्या पहिल्या नकारात्मक घटकाशी संबंधित आहे, जर डेक रिक्त असेल तर या विंडोमध्ये नकारात्मक घटक नसल्यास 0 प्रिंट करा.

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी = O (n)
स्पेस कॉम्प्लेक्सिटी = O (n)
जेथे n दिलेलेल्या अ‍ॅरे मधील घटकांची संख्या आहे.

येथे आपण रांग वापरल्यामुळे स्पेसची जटिलता रेषात्मक आहे. काळाची जटिलता म्हणून आम्ही इनपुटच्या सर्व घटकांमधून सहजपणे पुढे गेलो आहोत. अशा प्रकारे वेळेची जटिलता देखील रेषात्मक असते.

आकाराच्या प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक शोधण्यासाठी जावा कोड

import java.util.Deque;
import java.util.LinkedList;

class FirstNegativeIntegerInEveryWindowOfSizeK {
    private static void firstNegativeInteger(int[] arr, int k) {
        int n = arr.length;

        // create a deque q
        Deque<Integer> q = new LinkedList<>();
        // traverse the first window
        for (int i = 0; i < k; i++) {
            // if the current element is negative add it to the end of deque
            if (arr[i] < 0)
                q.addLast(i);
        }

        // if deque is not empty, front of deque is the index of first negative element
        // else there is no negative element in this window
        if (!q.isEmpty())
            System.out.print(arr[q.peek()] + " ");
        else
            System.out.print("0 ");

        for (int i = k; i < n; i++) {
            // remove previous window elements
            while (!q.isEmpty() && q.peek() <= (i - k)) {
                q.removeFirst();
            }

            // if the current element is negative, add it to the deque
            if (arr[i] < 0)
                q.addLast(i);

            // if deque is not empty, front of deque is the index of first negative element
            // else there is no negative element in this window
            if (!q.isEmpty())
                System.out.print(arr[q.peek()] + " ");
            else
                System.out.print("0 ");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, -2, 3, 4, -5};
        int k1 = 2;
        firstNegativeInteger(arr1, k1);

        // Example 2
        int arr2[] = new int[]{7, 9, -1, 2, 3, 4, -2, -3, -4};
        int k2 = 3;
        firstNegativeInteger(arr2, k2);
    }
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

आकाराच्या प्रत्येक विंडोमध्ये प्रथम नकारात्मक पूर्णांक शोधण्यासाठी सी ++ कोड

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

void firstNegativeInteger(int *arr, int k, int n) {
    // create a deque q
    deque<int> q;
    
    // traverse the first window
    for (int i = 0; i < k; i++) {
        // if the current element is negative add it to the end of deque
        if (arr[i] < 0)
            q.push_back(i);
    }
    
    // if deque is not empty, front of deque is the index of first negative element
    // else there is no negative element in this window
    if (!q.empty())
        cout<<arr[q.front()]<<" ";
    else
        cout<<"0 ";
        
    for (int i = k; i < n; i++) {
        // remove previous window elements
        while (!q.empty() && q.front() <= (i - k)) {
            q.pop_front();
        }
        
        // if the current element is negative, add it to the deque
        if (arr[i] < 0)
            q.push_back(i);
            
        // if deque is not empty, front of deque is the index of first negative element
        // else there is no negative element in this window
        if (!q.empty())
            cout<<arr[q.front()]<<" ";
        else 
            cout<<"0 ";
    }
    
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {5, -2, 3, 4, -5};
    int k1 = 2;
    firstNegativeInteger(arr1, k1, sizeof(arr1) / sizeof(arr1[0]));

    // Example 2
    int arr2[] = {7, 9, -1, 2, 3, 4, -2, -3, -4};
    int k2 = 3;
    firstNegativeInteger(arr2, k2, sizeof(arr2) / sizeof(arr2[0]));
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2