Как найти подряд идущие элементы

Как найти подряд идущие значения в массиве?

const arr = [
'значение 1',
'значение 3', 
'значение 1', 
'значение 2', 
'значение 1', 
'значение 4', 
'значение 1', 
'значение 6',
'значение 1', 
'значение 2']

let cnt = 0; //число совпадений
for(let i = arr.length-1; i > 0; i--) {
  if (arr[i] == 'значение 2' && arr[i-1] == 'значение 1') cnt++;
}

arr.reduce( (acc,v,i,a)=> i > 0 && v === 'значение 2' && a[i-1] === 'значение 1' ? acc + 1 : acc, 0)

Пригласить эксперта

• 
  Показать ещё
  Загружается…
  

aus

Гуру

(3991),
закрыт

12 лет назад

Похожие вопросы

В этой статье будет разобрана идея бинарного(двоичного) поиска на примере нескольких классических задач.

Основная идея

Допустим, у нас есть массив элементов и некоторая функция, которая по элементу возвращает либо True, либо False. Наложим на эту функцию условие – пусть сначала для всех элементов она возвращает True, а потом, начиная с какой-то позиции, возвращает только False. Иными словами, мы хотим работать с монотонной функцией. Проверим любой элемент, спросив значение функции от него. Если это True, то мы знаем, что все элементы левее него тоже будут давать такое значение. Аналогично с False, только мы получим информацию про элементы, которые правее нас.

Мы хотим найти позицию, где заканчивается True и начинается False. Заведем границы поиска – два указателя left и right. Будем поддерживать следующий инвариант: точка перехода лежит где-то на отрезке [left, right], значение в left всегда True, а в right всегда False. Будем проверять значение в середине текущего отрезка middle и сдвигать одну из границ поиска.

Если $F(middle) = False$, то сдвинем правую границу: $right = middle$. Иначе сдвинем левую $left=middle$. Заметим, что инвариант при этом продолжает выполняться.

Выбор границ бинарного поиска

Что делать, если функцию всегда истинна или всегда ложна на данном массиве? Нам необходимо поддерживать описанный выше инвариант. Будем считать, что в массиве есть фиктивные элементы перед самым первым элементом и после последнего элемента и скажем, что $F(-1) = True$, $F(n) = False$. Границы поиска изначально будут равны $left = -1$, $right = n$ (нумерация с нуля).

Перейдем от общих слов к примерам.

Задачи

Поиск первой единицы в массиве

У вас есть массив, состоящий из некоторого количества подряд идущих нулей, за которыми следует какое-то количество подряд идущих единиц. Вам нужно найти позицию первой единицы, то есть найти такое место, где заканчиваются нули, и начинаются единицы. Это можно сделать с помощью линейного поиска за один проход по массиву, но хочется сделать это быстрее с помощью бинарного поиска.
Посмотрим на элемент посередине массива. Если это нуль, то первую единицу стоит искать в правой половине массива, а если единица – то в левой. Решение этой задачи выглядит примерно так:

 1 int left = -1;
 2 int right = n;
 3 while (right - left > 1) {
 4     int middle = (left + right) / 2; //   формула среднего индекса
 5     if (a[middle] == 1) {
 6         right = middle; // right будет указывать на 1
 7     } else {
 8         left = middle; // left будет указывать на 0
 9     }
10 }

Поиск элемента в отсортированном массиве

Ведущий загадал число X от 1 до 100. Вы можете спросить, больше ли мое число чем число T, ведущий отвечает “да” или “нет”. За сколько вопросов в худшем случае вы сможете найти число X? Как нужно действовать?

Для решения используем ту же идею. В самом начале мы говорили о некоторой логической функции $F$, тут она определена достаточно четко.

$
F(a) = left{ begin{array}{c}
True, a < x \
False, a ge x\
end{array}
right.
$

По сути код предыдущего решения отличается лишь строкой 5, где вместо проверки a[middle] == 1 будет стоять a[middle] >= x.

В конце программы указатель $left$ будет стоять на последнем элементе, который меньше $X$, а $right$ – на первом элементе, который больше или равен $X$. Тогда проверим элемент $right$. Если он равен $X$, то $X$ есть в массиве, иначе – нет.

Асимптотика

Почему нужно делить обязательно пополам? Почему бы не спросить “число X больше, чем 80?” первым же вопросом? Но если вдруг ответ “нет”, то мы останемся с 80 вариантами вместо 100. То есть деление отрезка ровно пополам гарантирует, что в худшем случае мы останемся не более чем с половиной вариантов.

Так как отрезок поиска каждый раз уменьшается в два раза, то цикл while выполнится $O(log n)$ раз, где $log n$ – логарифм числа $n$.

Бинарный поиск по неотсортированному массиву

Переформулируем исходную задачу – теперь мы хотим просто найти пару соседних индексов, для одного из которых условие $P$ выполняется, а для другого нет. Здесь уже не требуется упорядоченность всего массива. По принципу непрерывности если для $L$ условие выполнялось, а для $R$ не выполнялось, то где-то между $L$ и $R$ найдется искомая позиция. Опять рассмотрим средний элемент $M$. Перейдем в одну из половин так, чтобы инваиант $P(L) neq P(R)$ выполнялся.

Например, если мы знаем, что $f(x_0) < 0$ и $f(x_1) > 0$, и функция непрерывная, то бинарным поиском можно найти ноль этой функции между $x_0$ и $x_1$, даже если функция не монотонная!

Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.

Задания

1. Какими будут границы $left$ и $right$ на массиве arr = {1, 3, 4, 10, 10, 10, 11, 80, 80, 81} для:
   1. $x = 1$
   2. $x = 10$
   3. $x = 20$
   4. $x = 79$
   5. $x = 80$
   6. $x = 5$
   7. $x = 81$
2. Придумайте, как с помощью бинарного поиска решить такие задачи:
   1. Найти **первое** число, равное X в отсортированном массиве, или вывести, что таких чисел нет
   2. Найти **последнее** число, равное X в отсортированном массиве, или вывести, что таких чисел нет
   3. Посчитать, сколько раз встречается число X в отсортированном массиве (в решении помогают два предыдущих пункта)
   4. Дан массив чисел, первая часть состоит из нечетных чисел, а вторая – из четных. Найти индекс, начиная с которого все числа четные.

Замечание
Все эти задачи решаются бинарным поиском за $O(log{n})$. Правда нужно понимать, что в чистом виде такую задачу решать двоичным поиском бессмысленно – ведь чтобы создать массив размера $n$, уже необходимо потратить $O(n)$ операций.

Поэтому зачастую такие задачи сформулированы таким образом:

Дан отсортированный массив размера $n$. Нужно ответить на $m$ запросов вида “встречается ли число $x_i$ в массиве n?”

Такая задача целиком решается за $O(n + mlog n)$

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko