K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇසොලයිට් ඇමේසන් පේපෑල් සොරොකෝ
අරා පෝලිමේ ස්ලයිඩින් කවුළුව

ගැටළු ප්රකාශය

“K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට ලබා දී ඇති බවයි අරාව ධනාත්මක හා negative ණ පූර්ණ සංඛ්‍යා අඩංගු වන අතර, k ප්‍රමාණයේ සෑම කවුළුවක්ම එම කවුළුවේ පළමු negative ණ නිඛිලය මුද්‍රණය කරයි. ඕනෑම කවුළුවක negative ණ පූර්ණ සංඛ්‍යාවක් නොමැති නම් ප්‍රතිදානය 0 (බිංදුව).

උදාහරණ

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

 

K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය

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) ට සමාන කැදැලි ලූපයක් ධාවනය කරන්න (ඇතුළත් කර නැත). මෙම ලූපය කවුළුව හරහා ගමන් කරයි i.
  3. Ar [j] හි අගය negative ණ නම් එය මුද්‍රණය කර කැඩී යයි, එසේ නොමැතිනම් ඊළඟ මූලද්‍රව්‍යය සඳහා දිගටම පරීක්ෂා කරන්න.
  4. කවුළුවක negative ණාත්මක අංගයක් නොමැති නම්, 0 මුද්‍රණය කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය = ඕ (n * k)
අභ්‍යවකාශ සංකීර්ණතාව = ඕ (1)
මෙහි n යනු දී ඇති අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

K ප්‍රමාණයේ සෑම කවුළුවක් සඳහාම අපි ස්වාධීනව ගැටළුව විසඳන බැවින්, අපි පොදුවේ n * k මූලද්‍රව්‍ය හරහා ගමන් කරන්නෙමු. මේ අනුව බහුපද කාල සංකීර්ණත්වය. අප කිසිවක් ගබඩා කර නොමැති බැවින් අවකාශයේ සංකීර්ණතාව නියත ය.

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

K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය සොයා ගැනීමට 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 negative ණාත්මක මූලද්‍රව්‍යයන්ගේ දර්ශක කවුළුවක ගබඩා කරයි. Deque හි පළමු අංගය කවුළුවේ පළමු negative ණ මූලද්‍රව්‍යයේ දර්ශකයට අනුරූප වේ. කවුළුව වෙනස් කරන අතරතුර, පෙර කවුළු මූලද්‍රව්‍යය Deque වෙතින් ඉවත් කර Deque වෙත නව අංගයක් එක් කරන්න. පළමු negative ණාත්මක මූලද්‍රව්‍යය පරීක්ෂා කිරීමේදී Deque හිස් නම්, 0 මුද්‍රණය කරන්න.

  1. සාදන්න ඩෙක් q. K ප්‍රමාණයේ පළමු කවුළුව සලකා බලන්න.
  2. පළමුවැන්නෙහි මූලද්රව්ය හරහා ගමන් කරන්න කවුළුව, මූලද්‍රව්‍යය negative ණ නම්, එහි දර්ශකය Deque අවසානය දක්වා තල්ලු කරන්න.
  3. සංචලනය අවසානයේ Deque හිස් මුද්‍රණය 0 නම්, එසේ නොමැතිනම් Deque හි පළමු මූලද්‍රව්‍යය පළමු negative ණ මූලද්‍රව්‍යයේ දර්ශකයට අනුරූප වේ.
  4. ඉතිරි අරාවෙහි ගමන් කරන්න (දර්ශකයේ k සිට n - 1 දක්වා ආරම්භ කරන්න), Deque හි ඉදිරිපස කොටස (i - k) ට වඩා අඩු නම් එය ඉවත් කරන්න. වත්මන් මූලද්රව්යය negative ණ නම්, එය Deque වෙත එක් කරන්න.
  5. Deque හි පළමු මූලද්රව්යය මෙම කවුළුව සඳහා පළමු negative ණාත්මක මූලද්රව්යයට අනුරූප වේ, Deque හිස් නම් මෙම කවුළුව තුළ negative ණාත්මක මූලද්රව්යයක් නොමැත, 0 මුද්රණය කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය = සාමාන්ය (n)
අභ්‍යවකාශ සංකීර්ණතාව = සාමාන්ය (n)
මෙහි n යනු දී ඇති අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

මෙන්න, අපි පෝලිමක් භාවිතා කර ඇති නිසා, අවකාශයේ සංකීර්ණතාව රේඛීය වේ. කාල සංකීර්ණතාව සම්බන්ධයෙන් ගත් කල, අපි සරලවම ආදානයේ සියලුම අංග හරහා ගමන් කර ඇත්තෙමු. මේ අනුව කාල සංකීර්ණතාව ද රේඛීය වේ.

K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය සොයා ගැනීමට ජාවා කේතය

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

K ප්‍රමාණයේ සෑම කවුළුවකම පළමු negative ණ නිඛිලය සොයා ගැනීමට 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