Подсчитайте отрицательные элементы, присутствующие в каждом подмассиве длины K

Опубликовано: 22 Сентября, 2022

Учитывая массив arr[] размера N и целое число K , задача состоит в том, чтобы подсчитать количество отрицательных элементов, присутствующих во всех подмассивах длины K.

Пример:

Input: arr[] = {-1, 2, -2, 3, 5, -7, -5}, K = 3
Output: 2 1 1 1 2
Explanation: 
First Subarray: {-1, 2, -2}. Count of negative numbers = 2.
Second Subarray: {2, -2, 3}. Count of negative numbers = 1.
Third Subarray: {-2, 3, 5}. Count of negative numbers = 1.
Fourth Subarray: {3, 5, -7}. Count of negative numbers = 1.
Fifth Subarray: {5, -7, -5}. Count of negative numbers = 2.

Input: arr[] = {-1, 2, 4, 4}, K = 2
Output: 1 0 0

Наивный подход: самый простой подход — пройти по заданному массиву, учитывая каждое окно размера K , и найдите количество отрицательных чисел в каждом окне.

Временная сложность: O(N*K)
Вспомогательное пространство: O(1)

Эффективный подход: эта проблема может быть решена с помощью техники скольжения окна. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную count как 0 , чтобы сохранить количество отрицательных элементов в окне размера K .
  • Инициализируйте две переменные i и j как 0 , чтобы сохранить первый и последний индекс окна соответственно.
  • Цикл, пока j<N и выполните следующие шаги:
    • Если arr[j] < 0 , увеличить счетчик на 1.
    • Если размер окна, т. е. j-i+1 , равен K , выведите значение count , и проверьте, если arr[i] < 0 , затем уменьшите count на 1. Также увеличьте i на 1.
    • Увеличьте значение j на 1.

Ниже приведена реализация вышеуказанного подхода

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ