Первое отрицательное целое число в каждом окне размера 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 (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. Если Deque пуста при проверке первого отрицательного элемента, выведите 0.

  1. Создать Deque 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