2sum с повторяющимися значениями

Question

Классический 2sum вопрос прост и хорошо известен:

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

и это всегда было сказано, что это может быть решено с использованием HashTable в O(N) времени & пространства сложности или O(NlogN) время и O(1) пространства сложность при первой сортировке, а затем двигается слева и справа,

хорошо эти два решения, очевидно, являются корр. ЭСТ, НО я думаю, не для следующего массива:

{1,1,1,1,1,1,1,1}

Можно ли печатать все пары, которые добавляют до 2 в этом массиве в O(N) или O(NlogN) временной сложности?

Answer 1

No, распечатка всех пар (включая дубликаты) принимает O(N2). Причина в том, что размер вывода равен O(N2), поэтому время работы не может быть меньше этого (поскольку для печати каждого элемента на выходе требуется некоторое количество времени, поэтому для простого вывода на печать потребуется CN2 = O(N2) времени).

Если все элементы одинаковые, например, {1,1,1,1,1}, каждая возможная пара будет на выходе:

1. 1 1 
2. 1 1 
3. 1  1 
4. 1  1 
5. 1 1 
6. 1 1 
7. 1  1 
8.  1 1 
9.  1 1 
10.  1 1 

Это N-1 + N-2 + ... + 2 + 1 (принимая каждый элемент со всеми элементами, справа), что
N(N-1)/2 = O(N2), что больше, чем O(N) или O(N log N).

Однако, вы должны быть в состоянии просто рассчитывать пары в ожидаемом O(N) по:

• Создание хэш-карта map отображение каждого элемента к графу, как часто она появляется.

• Перебор хэш-карты и суммируя, для каждого элемента x до S/2 (если идти до S мы будем включать пару x и S-x дважды, пусть map[x] == 0 если x не существует на карте):

  • map[x]*map[S-x], если x != S-x (что количество способов выбора x и S-x)
  • map[x]*(map[x]-1)/2, если x == S-x (от N(N-1)/2 выше).

Конечно, вы можете также печать на различных пар в O(N) путем создания хэш-карту, подобную выше и цикл через него, и только вывод x и S-x значение, если map[S-x] существует.

Answer 2

Отображения или хранение результатов является O (N 2 ) only.The худшего случая, как подчеркнуто вами, очевидно, имеет N пар и записать их на экране или хранить их в результирующем массив будет, несомненно, требует по крайней мере, столько времени. Короче говоря, вы правы! не

Answer 3

Нет

Вы можете предварительно вычислить их в O (NlogN) с помощью сортировки, но напечатать их, то Вам, возможно, потребуется больше, чем O (NlogN) .в худшем случае это может быть O (N^2). Давайте изменим алгоритм, чтобы найти все повторяющиеся пары.

В качестве примера:

a[ ]={ 2 , 4 , 3 , 2 , 9 , 3 , 3 } and sum =6 

После сортировки:

a[ ] = { 2 , 2 , 3 , 3 , 3 , 4 , 9 } 

Предположим, что вы нашли пару {2,4}, теперь вы должны найти счетчик 2 и 4 и умножить их, чтобы получить нет двух повторяющихся пар. Здесь 2 происходит 2 раза, а 1 - 1 раз. В результате получается 2 {1} 2 * 1 = 2 раза. Теперь рассмотрим частный случай, когда оба числа совпадают, а затем подсчитывают число встречаемости и sq их . Здесь {3,3} сумма до 6. Вхождение 3 в массив равно 3.Hence {3,3} будет отображаться 9 раз на выходе.

В вашем массиве {1,1,1,1,1} только пара {1,1} будет суммироваться до 2, а число 1 равно 5. Когда идут 5^2 = 25 пар {1 , 1} на выходе.