साइज के प्रत्येक विन्डोमा पहिलो नकारात्मक पूर्णांक


कठिनाई तह मध्यम
बारम्बार सोधिन्छ समग्र अमेजन PayPal सोरोको
एरे लाम स्लाइडि Wind विन्डो

समस्या वक्तव्य

समस्या "आकार k को प्रत्येक विन्डोमा पहिलो नकारात्मक पूर्णांक" भन्छन कि तपाईंलाई एक दिइन्छ array सकरात्मक र नकारात्मक पूर्णांकहरू समावेश गर्दै, साइजको प्रत्येक विन्डोका लागि त्यो विन्डोमा पहिलो नकारात्मक इन्टिजर प्रिन्ट गर्दछ। यदि कुनै विन्डोमा कुनै नकारात्मक पूर्णांक छैन भने आउटपुट ० (शून्य)।

उदाहरण

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

भोली दृष्टिकोण

साइज k को प्रत्येक विन्डोका लागि, विन्डोको सबै एलिमेन्टहरूको माध्यमबाट पार गर्नुहोस् र पहिलो नकारात्मक इन्टिजर प्रिन्ट गर्नुहोस्।

  1. I बराबर ० लाई (n - k) को लागी एउटा लूप चलाउनुहोस्, यहाँ प्रत्येक म साइज k को विन्डोसँग सम्बन्धित छ।
  2. J को लागि i मा (i + k) बराबरको लागि नेस्टेड लूप चलाउनुहोस् (समावेश गरिएको छैन)। यो लूप विन्डोज i लाई ट्रान्सवर्स गर्दछ
  3. यदि अरर [j] को मान नकारात्मक छ भने यसलाई प्रिन्ट गर्नुहोस् र ब्रेक गर्नुहोस्, अन्य तत्वको लागि जाँच गर्न जारी राख्नुहोस्।
  4. यदि त्यहाँ विन्डोमा कुनै नकारात्मक तत्व छैन भने, ० प्रिन्ट गर्नुहोस्।

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

समय जटिलता = O (n * k)
ठाउँ जटिलता = O (१)
जहाँ n दिइएको एर्रेमा एलिमेन्ट्सको संख्या हो।

किनकि हामी आकार k को प्रत्येक विन्डोको लागि समस्यालाई स्वतन्त्र रूपमा समाधान गर्दैछौं, हामी सामान्य रूपमा n * k एलिमेन्टहरूमार्फत ट्राभर्स गर्दैछौं। र यसरी बहुपद समय जटिलता। र किनकि हामीले केहि पनि भण्डार गरेका छैनौं खाली ठाउँ जटिलता स्थिर छ।

जाभा कोड साइज k को हरेक विन्डोमा पहिलो पहिलो नकारात्मक पूर्णांक फेला पार्न

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

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

#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 को पहिलो तत्व विन्डो मा पहिलो नकारात्मक तत्व को सूचकांक संग मेल खान्छ। विन्डो परिवर्तन गर्ने क्रममा, अघिल्लो विन्डो एलिमेन्ट डेकबाट हटाउनुहोस् र नयाँ एलिमेन्ट ड्यूकमा थप्नुहोस्। यदि Deque खाली छ पहिलो नकारात्मक तत्व को लागी जाँच गर्दा, ० प्रिन्ट गर्नुहोस्।

  1. एक सिर्जना गर्नुहोस् Deque q आकार k को पहिलो विन्डोलाई विचार गर्नुहोस्।
  2. पहिलो को तत्वहरु पार गर्नुहोस् विन्डो, यदि तत्व नकारात्मक छ, यसको अनुक्रमणिका को Deque को अन्तमा पुश गर्नुहोस्।
  3. Traversal को अन्त्यमा यदि Deque खाली प्रिन्ट ० छ, अन्यथा Deque मा पहिलो एलिमेन्ट पहिलो नकारात्मक तत्वको अनुक्रमणिका अनुरूप छ।
  4. बाँकी एर्रेमा ट्रान्सभर्स (अनुक्रमणिका k बाट n - १ सम्म सुरु गर्नुहोस्), जब कि Deque को अगाडि (i - k) हटाउने भन्दा कम छ। यदि हालको तत्व नकारात्मक छ भने, यसलाई Deque मा थप्नुहोस्।
  5. Deque मा पहिलो तत्व यस विन्डो को लागी पहिलो नकारात्मक तत्व संग मेल खान्छ, यदि Deque खाली छ भने, यो विन्डोमा कुनै नकारात्मक तत्व छैन, प्रिन्ट ०।

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

समय जटिलता = ऊ)
ठाउँ जटिलता = ऊ)
जहाँ n दिइएको एर्रेमा एलिमेन्ट्सको संख्या हो।

यहाँ, किनकि हामीले कतार प्रयोग गरेका छौं, स्पेस जटिलता रैखिक छ। समय जटिलताको रूपमा, हामी केवल इनपुट को सबै तत्वहरु को माध्यम बाट पार गरेका छौं। यसैले समय जटिलता पनि रैखिक हुन्छ।

जाभा कोड साइज k को हरेक विन्डोमा पहिलो नकारात्मक इन्टिजर पत्ता लगाउन

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

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

#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