Подсчет количества идентичных пар

Question

Идентичный пара в массиве 2 индексов p,q таким образом, что

0<=p<q<N и array[p]=array[q] где N длина массива.

Учитывая несортированный массив, найдите число одинаковых пар в массиве.

Моим решением было сортировать массив по значениям, отслеживать индексы.

Тогда для каждого индекса p в отсортированном массиве, посчитайте все q<N таким образом, что и

sortedarray[p].index < sortedarray[q].index and 
sortedarray[p] = sortedarray[q] 

Является ли это правильный подход. Я думаю, что сложность будет

O(N log N) for sorting based on value + 

O(N^2) for counting the newsorted array that satisfies the condition. 

Это значит, что я все еще смотрю O(N^2). Есть ли способ лучше ?

Еще одна мысль, которая пришла, заключалась в том, что каждый P-бинарный поиск сортировал массив для всех Q, который удовлетворяет условию. Разве это не уменьшить сложность второй части к O(Nlog(N))

Вот мой код для второй части

for(int i=0;i<N;i++){ 

        int j=i+1; 

      while(j<N && sortedArray[j].index > sortedArray[i].index && 
        sortedArray[j].item == sortedArray[i].item){ 

         inversion++; 
         j++; 
      } 
     } 
    return inversion; 

@Edit: Я думаю, я перепутал сложность второй части будет O(N^2).

Как и в каждой итерации во время цикла, не происходит повторного сканирования элементов из индексов 0-i, для сканирования отсортированного массива для подсчета инверсий требуется линейное время. Таким образом, общая сложность

O(NlogN) для сортировки и O(N) для линейного сканирования в сортированном массиве.

Answer 1

Вы частично верны. Сортировка массива с помощью Merge Sort или Heapsort займет O(n lg n). Но как только массив отсортирован, вы можете сделать один проход, чтобы найти все одинаковые пары. Этот единственный проход является операцией O(n). Таким образом, общая сложность:

O(n lg n + n) = O(n lg n)

Answer 2

Если вы можете выделить больше памяти, вы можете получить некоторые выгоды.

Вы можете достичь O(n) с помощью хеш-таблицы, которая отображает любые значения в массиве на счетчик, указывающий, как часто вы уже видели это значение.

Если количество допустимых значений является целым и в ограниченном диапазоне, вы можете напрямую использовать массив вместо хеш-таблицы. Индекс значения i составляет i. В этом случае сложность будет O(n+m), где m - это число допустимых значений (потому что вы должны сначала установить 0 все записи в массиве, а затем просмотреть все записи массива для подсчета пар).

Оба метода дают вам количество одинаковых значений для каждого значения в вашем массиве. Назовем этот номер nv_i номером появления значения i в массиве.Затем число пар значений i: (nv_i)*(nv_i-1)/2.

Вы можете спарить:

1st i with nv_i-1 others 
2nd i with nv_i-2 others 
... 
last i with 0 

И (nv_i-1)+(nv_i-2)+...+0 = (nv_i)*(nv_i-1)/2

Answer 3

Как Тим отмечает в своем ответе, сложность нахождения пары в отсортированном массиве O(n) и не O(n^2).

Чтобы убедиться в этом, подумайте о типичном алгоритме O(n^2): Insertion Sort.

Анимированный пример можно найти here.

Как вы можете видеть в формате GIF, поэтому этот алгоритм является квадратным, потому, что для каждого элемента, он должен проверить весь массив, чтобы гарантировать, где такой элементу придется идти (это включает предыдущих элементов в массиве!).

В руке у вас есть упорядоченный массив: например. [0,1,3,3,6,7,7,9,10,10]

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

Таким образом, вы сканировать весь массив только один раз: O(n)

Answer 4

Я думал об этом .... Я думаю, что если вы «встраивать» условие == в свой алгоритм сортировки, то, сложность все еще O (n lg n).