Першае адмоўнае цэлае лік у кожным акне памерам k


Узровень складанасці серада
Часта пытаюцца ў Акаліта амазонка PayPal Сарока
масіў чаргу Рассоўнае акно

Пастаноўка праблемы

У задачы "Першае адмоўнае цэлае лік у кожным акне памерам k" гаворыцца, што вам дадзена масіў якія ўтрымліваюць дадатныя і адмоўныя цэлыя лікі, для кожнага акна памерам k надрукуйце першае адмоўнае цэлае лік у гэтым акне. Калі ў любым акне няма цэлага адмоўнага ліку, вывядзіце 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), тут кожнаму i адпавядае акно памерам k.
  2. Выканаць укладзены цыкл для j, роўнага i да (i + k) (не ўваходзіць). Гэты цыкл праходзіць праз акно i.
  3. Калі значэнне arr [j] адмоўнае, надрукуйце яго і разбярыце, інакш працягвайце правяраць наступны элемент.
  4. Калі ў акне няма адмоўнага элемента, надрукуйце 0.

Аналіз складанасці

Складанасць часу = O (n * k)
Касмічная складанасць = O (1)
дзе n - колькасць элементаў у дадзеным масіве.

Паколькі мы вырашаем задачу самастойна для кожнага акна памерам k, мы праходзім па n * k элементаў у цэлым. І, такім чынам, шматчленная складанасць часу. І паколькі мы нічога не захавалі, складанасць касмічнай прасторы сталая.

Код Java для пошуку першага першага адмоўнага цэлага ліку ў кожным акне памерам 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 ++ для пошуку першага адмоўнага цэлага ліку ў кожным акне памерам k

#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, а таксама дадайце новы элемент у Deque. Калі Deque пусты падчас праверкі першага адмоўнага элемента, надрукуйце 0.

  1. Стварыць Дэка q. Разгледзім першае акно памерам k.
  2. Абяжыце элементы першага акно, калі элемент адмоўны, націсніце яго індэкс у канец Deque.
  3. У канцы развароту, калі Deque пусты, надрукуйце 0, інакш першы элемент Deque адпавядае індэксу першага адмоўнага элемента.
  4. Траверс у пакінутым масіве (пачынаючы з індэкса k да n - 1), а пярэдняя частка Deque менш (i - k) выдаляе яго. Калі бягучы элемент адмоўны, дадайце яго ў Deque.
  5. Першы элемент у Deque адпавядае першаму адмоўнаму элементу для гэтага акна, калі Deque пусты, у гэтым акне няма адмоўнага элемента, надрукуйце 0.

Аналіз складанасці

Складанасць часу = Аб (п)
Касмічная складанасць = Аб (п)
дзе n - колькасць элементаў у дадзеным масіве.

Тут, паколькі мы выкарыстоўвалі чаргу, складанасць прасторы лінейная. Што тычыцца складанасці ў часе, мы проста абышлі ўсе элементы ўваходных дадзеных. Такім чынам, складанасць часу таксама лінейная.

Код Java для пошуку першага адмоўнага цэлага ліку ў кожным акне памерам 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 ++ для пошуку першага адмоўнага цэлага ліку ў кожным акне памерам k

#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