K വലുപ്പമുള്ള ഓരോ വിൻഡോയിലും ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ പേപാൽ സോറോക്കോ
അറേ വരി സ്ലൈഡിംഗ് വിൻഡോ

പ്രശ്നം പ്രസ്താവന

“K വലുപ്പമുള്ള എല്ലാ വിൻഡോകളിലെയും ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി പോസിറ്റീവ്, നെഗറ്റീവ് സംഖ്യകൾ അടങ്ങിയിരിക്കുന്നു, കാരണം വലുപ്പമുള്ള ഓരോ വിൻഡോയ്ക്കും ആ വിൻഡോയിലെ ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ പ്രിന്റുചെയ്യുക. ഏതെങ്കിലും വിൻ‌ഡോയിൽ‌ നെഗറ്റീവ് ഇൻ‌റിജർ‌ ഇല്ലെങ്കിൽ‌ output ട്ട്‌പുട്ട് 0 (പൂജ്യം).

ഉദാഹരണങ്ങൾ

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

 

K വലുപ്പമുള്ള ഓരോ വിൻഡോയിലും ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ

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

നിഷ്കളങ്കമായ സമീപനം

K വലുപ്പമുള്ള ഓരോ വിൻഡോയ്‌ക്കും, വിൻഡോയുടെ എല്ലാ ഘടകങ്ങളിലൂടെയും സഞ്ചരിച്ച് ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ പ്രിന്റുചെയ്യുക.

  1. I 0 മുതൽ (n - k) വരെ തുല്യമായ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക, ഇവിടെ ഓരോന്നും ഞാൻ k വലുപ്പമുള്ള ഒരു വിൻഡോയുമായി യോജിക്കുന്നു.
  2. J എന്നതിന് തുല്യമായ ഒരു നെസ്റ്റഡ് ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക (i + k) (ഉൾപ്പെടുത്തിയിട്ടില്ല). ഈ ലൂപ്പ് വിൻഡോയിലൂടെ സഞ്ചരിക്കുന്നു.
  3. Arr [j] ന്റെ മൂല്യം നെഗറ്റീവ് ആണെങ്കിൽ അത് പ്രിന്റുചെയ്‌ത് തകർക്കുക, അല്ലെങ്കിൽ അടുത്ത ഘടകത്തിനായി പരിശോധിക്കുന്നത് തുടരുക.
  4. ഒരു വിൻഡോയിൽ നെഗറ്റീവ് ഘടകങ്ങളൊന്നുമില്ലെങ്കിൽ, 0 പ്രിന്റുചെയ്യുക.

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n * k)
ബഹിരാകാശ സങ്കീർണ്ണത = O (1)
ഇവിടെ 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

കെ വലുപ്പമുള്ള ഓരോ വിൻഡോയിലും ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ കണ്ടെത്താനുള്ള സി ++ കോഡ്

#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 സംഭരിക്കുന്നു. ഡെക്യൂവിന്റെ ആദ്യ ഘടകം വിൻഡോയിലെ ആദ്യത്തെ നെഗറ്റീവ് മൂലകത്തിന്റെ സൂചികയുമായി യോജിക്കുന്നു. വിൻ‌ഡോ മാറ്റുമ്പോൾ‌, ഡെക്യൂവിൽ‌ നിന്നും മുമ്പത്തെ വിൻ‌ഡോ എലമെൻറ് നീക്കംചെയ്യുക, കൂടാതെ ഡെക്യൂവിലേക്ക് പുതിയ എലമെൻറ് ചേർക്കുക. ആദ്യത്തെ നെഗറ്റീവ് ഘടകത്തിനായി പരിശോധിക്കുമ്പോൾ ഡെക്ക് ശൂന്യമാണെങ്കിൽ, 0 പ്രിന്റുചെയ്യുക.

  1. സൃഷ്ടിക്കുക ഡെക്ക് q. K വലുപ്പത്തിന്റെ ആദ്യ വിൻഡോ പരിഗണിക്കുക.
  2. ആദ്യത്തേതിന്റെ ഘടകങ്ങൾ സഞ്ചരിക്കുക ജാലകം, മൂലകം നെഗറ്റീവ് ആണെങ്കിൽ, അതിന്റെ സൂചിക ഡെക്യൂവിന്റെ അവസാനത്തിലേക്ക് തള്ളുക.
  3. ട്രാവെർസലിന്റെ അവസാനത്തിൽ ഡെക്ക് ശൂന്യമായ പ്രിന്റ് 0 ആണെങ്കിൽ, ഡെക്കിലെ ആദ്യ ഘടകം ആദ്യത്തെ നെഗറ്റീവ് മൂലകത്തിന്റെ സൂചികയുമായി യോജിക്കുന്നു.
  4. ശേഷിക്കുന്ന അറേയിൽ സഞ്ചരിക്കുക (സൂചിക k മുതൽ n - 1 വരെ ആരംഭിക്കുക), Deque- ന്റെ മുൻഭാഗം (i - k) എന്നതിനേക്കാൾ കുറവാണെങ്കിൽ അത് നീക്കംചെയ്യുക. നിലവിലെ ഘടകം നെഗറ്റീവ് ആണെങ്കിൽ, അത് ഡെക്യൂവിൽ ചേർക്കുക.
  5. Deque- ലെ ആദ്യ ഘടകം ഈ വിൻഡോയുടെ ആദ്യ നെഗറ്റീവ് ഘടകവുമായി പൊരുത്തപ്പെടുന്നു, Deque ശൂന്യമാണെങ്കിൽ ഈ വിൻഡോയിൽ നെഗറ്റീവ് ഘടകങ്ങളൊന്നുമില്ല, 0 പ്രിന്റുചെയ്യുക.

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n)
ബഹിരാകാശ സങ്കീർണ്ണത = O (n)
ഇവിടെ 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

കെ വലുപ്പമുള്ള ഓരോ വിൻഡോയിലും ആദ്യത്തെ നെഗറ്റീവ് സംഖ്യ കണ്ടെത്താനുള്ള സി ++ കോഡ്

#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