Алгоритмы. Посчитать все пары одинаковых чисел в отсортированном массиве за O (n)? ⇐ JAVA

[Anonymous]

Вопрос, который заставил меня задуматься, заключается в следующем:

Предположим, у нас есть отсортированный массив с числами {1,1,1,1,2,2. ,4,4,4}.

Теперь, учитывая, что мы ясно видим, что у нас есть шесть пар единиц, одна пара двоек и три пары четверок (10 пары). Как бы вы построили алгоритм, который находит эти пары за O(n)?

У меня есть алгоритм, который подсчитывает пары в массиве и делает это следующим образом:

Код: Выделить всё

Arrays.sort(array);
int counter = 0;
for(int i = 0; i

Подробнее здесь: [url]https://stackoverflow.com/questions/46425980/algorithms-count-all-pairs-of-equal-numbers-in-a-sorted-array-in-on[/url]