Подсчет непересекающихся подмассивов размера K с равными альтернативными элементами
Учитывая массив arr[] длины N , задача состоит в том, чтобы найти количество непересекающихся подмассивов размера K , таких что альтернативные элементы равны.
Примеры:
Input: arr[] = {2, 4, 2, 7}, K = 3
Output: 1
Explanation: Given subarray {2, 4, 2} is a valid array because the elements in even position(index no.0 and 2) are equal. Hence the count of the subarrays with size K = 3 is 1.Input: arr[] = {5, 2, 5, 2, 3, 9, 7, 9, 7}, K = 4
Output: 2
Explanation: Subarray {5, 2, 5, 2} and {9, 7, 9, 7} are valid subarrays because the elements in even position(index no.0 and 2) and odd positions(index no.1 and 3) are equal. Hence the count of the subarrays with size K = 4 is 2.
Подход: реализуйте приведенную ниже идею, чтобы решить проблему.
Initially find all the non-overlapping subarrays where alternate elements are equal. Comparing the lengths of each such subarray with K, we can find out how many valid subarrays of size K can be extracted from each of those.
Для реализации идеи выполните следующие шаги:
- Инициализируйте t = 2 в начале и c = 0, чтобы поддерживать количество подмассивов.
- Перебрать массив из индекса 2.
- Всякий раз, когда мы находим arr[i] = arr[i-2], увеличиваем t на 1.
- Когда t станет равным K , увеличьте c на 1 и сбросьте t = 0 .
- Если длина данного массива arr[] меньше 2, см. значение K и соответственно верните вывод.
- После итерации по массиву верните c в качестве подмассивов счетчика.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)
Статьи по Теме:
- Введение в массивы - учебные пособия по структурам данных и алгоритмам