Найти количество диапазонов (a [i], a [i + 1]), которое содержит значение k для i в диапазоне a, b

Question

Учитывая массив из n элементов, как мне найти количество диапазонов [min (A [i], A [i + 1]), max (A [i], A [i + 1])]], которые содержит заданное значение k. Здесь i лежит между 0 <= a <b <n для индексации с нуля, где a и b являются индексами с нуля. </p>

Например, для массива ниже с a = 1 и b = 3 ;

6 3 2 8 5

Предположим, что для k = 3 его нужно найти в диапазоне [min (A [1], A [2]), max (A [1 ], A [2])] и [min (A [2], A [3]), max (A [2], A [3])]. Здесь k = 3 появляется в обоих диапазонах [2, 3] и [2, 8], поэтому ответ равен 2.

Как я могу найти количество диапазонов за менее чем линейное время при определенных предварительных вычислениях ?

Мне не нужен точный код, достаточно сделать общий обзор подхода / структуры данных.

Заранее спасибо!

Answer 1

Вы можете сэкономить время, предварительно выбив все элементы i массива A , которые заполняют (A[i-1] <= A[i] and A[i] <= A[i+1]) or ((A[i-1] >= A[i] and A[i] >= A[i+1]). Тогда подсчет действительного номера диапазона интервалов должен быть таким же.

int ctr = 0; 
for(i=a;i<b-1;i++) 
{ 
  if ( (A[i]<=k && A[i+1]>= k) ||  (A[i]>=k && A[i+1]<= k) ) 
    ctr++; 
} 
printf(" Count: %i", ctr);