ಕೆ ಗಾತ್ರದ ಪ್ರತಿ ವಿಂಡೋದಲ್ಲಿ ಮೊದಲ ನಕಾರಾತ್ಮಕ ಪೂರ್ಣಾಂಕ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಅಮೆಜಾನ್ ಪೇಪಾಲ್ ಸೊರೊಕೊ
ಅರೇ ಕ್ಯೂ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಗಾತ್ರದ k ನ ಪ್ರತಿ ವಿಂಡೋದಲ್ಲಿ ಮೊದಲ negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕ” ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಸರಣಿ ಧನಾತ್ಮಕ ಮತ್ತು negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಗಾತ್ರದ ಪ್ರತಿ ಕಿಟಕಿಗೆ ಆ ವಿಂಡೋದಲ್ಲಿ ಮೊದಲ negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕವನ್ನು ಮುದ್ರಿಸುತ್ತದೆ. ಯಾವುದೇ ವಿಂಡೋದಲ್ಲಿ negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕವಿಲ್ಲದಿದ್ದರೆ output ಟ್‌ಪುಟ್ 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

ನಿಷ್ಕಪಟ ಅಪ್ರೋಚ್

ಗಾತ್ರದ k ನ ಪ್ರತಿ ವಿಂಡೋಗೆ, ವಿಂಡೋದ ಎಲ್ಲಾ ಅಂಶಗಳ ಮೂಲಕ ಸಂಚರಿಸಿ ಮತ್ತು ಮೊದಲ negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕವನ್ನು ಮುದ್ರಿಸಿ.

  1. ನಾನು 0 ರಿಂದ (n - k) ಗೆ ಸಮನಾಗಿರುವ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ, ಇಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ನಾನು ಗಾತ್ರದ k ನ ವಿಂಡೋಗೆ ಅನುರೂಪವಾಗಿದೆ.
  2. J ಗೆ ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ i ಗೆ (i + k) ಸಮನಾಗಿರುತ್ತದೆ (ಸೇರಿಸಲಾಗಿಲ್ಲ). ಈ ಲೂಪ್ ವಿಂಡೋವನ್ನು ಹಾದುಹೋಗುತ್ತದೆ.
  3. ಅರ್ [ಜೆ] ನ ಮೌಲ್ಯವು negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ ಅದನ್ನು ಮುದ್ರಿಸಿ ಮುರಿಯಿರಿ, ಇಲ್ಲದಿದ್ದರೆ ಮುಂದಿನ ಅಂಶವನ್ನು ಪರಿಶೀಲಿಸುವುದನ್ನು ಮುಂದುವರಿಸಿ.
  4. ವಿಂಡೋದಲ್ಲಿ ಯಾವುದೇ negative ಣಾತ್ಮಕ ಅಂಶವಿಲ್ಲದಿದ್ದರೆ, 0 ಅನ್ನು ಮುದ್ರಿಸಿ.

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ = ಒ (ಎನ್ * ಕೆ)
ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ = ಒ (1)
ಇಲ್ಲಿ n ಎಂಬುದು ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ಗಾತ್ರದ k ನ ಪ್ರತಿ ವಿಂಡೋಗೆ ನಾವು ಸ್ವತಂತ್ರವಾಗಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತಿರುವುದರಿಂದ, ನಾವು ಸಾಮಾನ್ಯವಾಗಿ n * k ಅಂಶಗಳ ಮೂಲಕ ಸಂಚರಿಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಬಹುಪದ ಸಮಯದ ಸಂಕೀರ್ಣತೆ. ಮತ್ತು ನಾವು ಏನನ್ನೂ ಸಂಗ್ರಹಿಸದ ಕಾರಣ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.

ಕೆ ಗಾತ್ರದ ಪ್ರತಿ ವಿಂಡೋದಲ್ಲಿ ಮೊದಲ ಮೊದಲ negative ಣಾತ್ಮಕ ಪೂರ್ಣಾಂಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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 ಣಾತ್ಮಕ ಅಂಶಗಳ ಸೂಚಿಕೆಗಳನ್ನು ವಿಂಡೋದಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಡೆಕ್ನ ಮೊದಲ ಅಂಶವು ವಿಂಡೋದಲ್ಲಿನ ಮೊದಲ negative ಣಾತ್ಮಕ ಅಂಶದ ಸೂಚ್ಯಂಕಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ. ವಿಂಡೋವನ್ನು ಬದಲಾಯಿಸುವಾಗ, ಹಿಂದಿನ ವಿಂಡೋ ಅಂಶವನ್ನು ಡೆಕ್ಯೂನಿಂದ ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಹೊಸ ಅಂಶವನ್ನು ಡೆಕ್ಯೂಗೆ ಸೇರಿಸಿ. ಮೊದಲ ನಕಾರಾತ್ಮಕ ಅಂಶವನ್ನು ಪರಿಶೀಲಿಸುವಾಗ ಡೆಕ್ಯೂ ಖಾಲಿಯಾಗಿದ್ದರೆ, 0 ಅನ್ನು ಮುದ್ರಿಸಿ.

  1. ಒಂದು ರಚಿಸಿ ಡೆಕ್ಯೂ q. ಕೆ ಗಾತ್ರದ ಮೊದಲ ವಿಂಡೋವನ್ನು ಪರಿಗಣಿಸಿ.
  2. ಮೊದಲನೆಯ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗಿರಿ ವಿಂಡೋ, ಅಂಶವು negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ, ಅದರ ಸೂಚಿಯನ್ನು ಡೆಕ್ನ ಅಂತ್ಯಕ್ಕೆ ತಳ್ಳಿರಿ.
  3. ಟ್ರಾವೆರ್ಸಲ್ನ ಕೊನೆಯಲ್ಲಿ ಡೆಕ್ ಖಾಲಿ ಮುದ್ರಣ 0 ಆಗಿದ್ದರೆ, ಇಲ್ಲದಿದ್ದರೆ ಡೆಕ್ನಲ್ಲಿನ ಮೊದಲ ಅಂಶವು ಮೊದಲ negative ಣಾತ್ಮಕ ಅಂಶದ ಸೂಚ್ಯಂಕಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ.
  4. ಉಳಿದ ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಚರಿಸಿ (ಸೂಚ್ಯಂಕ k ನಿಂದ n - 1 ರವರೆಗೆ ಪ್ರಾರಂಭಿಸಿ), ಆದರೆ Deque ನ ಮುಂಭಾಗವು (i - k) ಗಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ಅದನ್ನು ತೆಗೆದುಹಾಕಿ. ಪ್ರಸ್ತುತ ಅಂಶ negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ, ಅದನ್ನು ಡೆಕ್ಯೂಗೆ ಸೇರಿಸಿ.
  5. ಡೆಕ್ನಲ್ಲಿನ ಮೊದಲ ಅಂಶವು ಈ ವಿಂಡೋದ ಮೊದಲ negative ಣಾತ್ಮಕ ಅಂಶಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ, ಡೆಕ್ಯೂ ಖಾಲಿಯಾಗಿದ್ದರೆ ಈ ವಿಂಡೋದಲ್ಲಿ ಯಾವುದೇ ನಕಾರಾತ್ಮಕ ಅಂಶಗಳಿಲ್ಲ, 0 ಅನ್ನು ಮುದ್ರಿಸಿ.

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ = ಓ (ಎನ್)
ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ = ಓ (ಎನ್)
ಇಲ್ಲಿ 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