Први негативни цели број у сваком прозору величине к


Ниво тешкоће Средњи
Често питани у Аццолите амазонка ПаиПал Сороцо
Ред Ред Клизни прозор

Изјава о проблему

Проблем „Први негативни цели број у сваком прозору величине к“ наводи да вам је дато поредак који садрже позитивне и негативне целе бројеве, за сваки прозор величине к исписујемо прву негативну целу вредност у том прозору. Ако у било којем прозору нема негативног целог броја, онда испишите 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. Покрените угнежђену петљу за ј једнако и до (и + к) (није укључено). Ова петља пролази кроз прозор и.
  3. Ако је вредност арр [ј] негативна, испишите је и прекините, у супротном наставите да тражите следећи елемент.
  4. Ако у прозору нема негативног елемента, одштампајте 0.

Анализа сложености

Сложеност времена = О (н * к)
Сложеност простора = О (1)
где је н број елемената у датом низу.

Будући да проблем решавамо независно за сваки прозор величине к, прелазимо кроз н * к елементе уопште. А самим тим и полиномска временска сложеност. А пошто нисмо ништа ускладиштили, сложеност простора је константна.

Јава код за проналажење првог првог негативног целог броја у сваком прозору величине к

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

Оптималан приступ

Оптимални приступ за решавање горе наведеног проблема је употреба технике Декуе и клизних прозора. Декуе складишти индексе негативних елемената у прозору. Први елемент Декуе-а одговара индексу првог негативног елемента у прозору. Док мењате прозор, уклоните претходни елемент прозора из Декуе-а и такође додајте нови елемент у Декуе. Ако је Декуе празан док се проверава да ли постоји први негативни елемент, одштампајте 0.

  1. Креирање Декуе к. Размотримо први прозор величине к.
  2. Пређите елементе првог прозор, ако је елемент негативан, гурните његов индекс на крај Декуе-а.
  3. На крају преласка ако је Декуе празан, исписује се 0, иначе први елемент у Декуеу одговара индексу првог негативног елемента.
  4. Прелазак у преостали низ (започните од индекса к до н - 1), док је предњи део Декуеа мањи од (и - к) и уклања га. Ако је тренутни елемент негативан, додајте га у Декуе.
  5. Први елемент у Декуе одговара првом негативном елементу за овај прозор, ако је Декуе празан, у овом прозору нема негативног елемента, исписати 0.

Анализа сложености

Сложеност времена = Он)
Сложеност простора = Он)
где је н број елемената у датом низу.

Овде, јер смо користили ред, сложеност простора је линеарна. Што се тиче временске сложености, једноставно смо прешли кроз све елементе уноса. Стога је временска сложеност такође линеарна.

Јава код за проналажење првог негативног целог броја у сваком прозору величине к

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