Алгоритм получения нового списка, не содержащего дублирующегося элемента, путем добавления любых 2 элементов в большой массив

Question

Я могу думать только об этом наивном алгоритме. Есть ли лучший способ? C / C ++, Ruby, Haskell в порядке.

arry = [1,5,.....4569895] //1000000 elements ,sorted , no duplicated
newArray = Hash.new
for (i = 0 ; i < arry.length ;i++ )
{
       for (j = 0 ; j < arry.length ;j ++ )
       {
                elem = arry[i] + arry[j]
                if (! newArray.key?(elem))
                {
                    newArray [elem] = arry[i] + arry[j]
                }

       }

}

РЕДАКТИРОВАТЬ: извините. У меня есть дискретное значение в массиве, вместо [1..1000000]

Answer 1

Было бы более эффективно разделить алгоритм на два отдельных этапа. (Предупреждение: псевдокод вперед)

Сначала создайте n-1 списки, добавив остальные элементы в i-й элемент. Это можно сделать параллельно для каждого списка. Обратите внимание, что результирующие списки будут отсортированы.

newArray = array(array.length);
for (i = 0 ; i < array.length ;i++ ) {
  newArray[i] = array(array.length - i - 1);
  for (j = 0; j < array.length - i; j++) {
    newArray[i][j] = array[i] + array[j + i];
  }
}

Второе использование сортировка слиянием в для объединения полученных списков. Вы можете сделать это параллельно, например, объединить newArray [0] - newArray [i], newArray [2] - newArray [1-i], ... и снова, пока у вас не будет только одного списка.

Answer 2

Существует одна очевидная оптимизация: запустите второй цикл по индексу i, чтобы избежать x + y и y + x.

Тогда, если вы не хотите использовать набор, вы можете использовать тот факт, что элементы отсортированы, чтобы вы могли создавать N списков и объединять их, удаляя дубликаты.

Answer 3

Боюсь, лучшая временная сложность в худшем случае - O (n ² ). Для ввода {2 ⁰ , 2 ¹ , 2 ² , ...} вы не получите дубликат при добавлении этих чисел. Предполагая, что хэш-вставки равны O (1), у вас уже есть лучший алгоритм ...

Answer 4

Если условие говорит о том, что вы должны иметь возможность добавить любой элемент в диапазон, то единственный способ, о котором я могу подумать, - это проверить, не находится ли сумма в списке результатов. Поскольку для любого числа x, есть x различных дополнений, которые приводят к x. (Или х / 2, если вы считаете, что 1 + 2 и 2 + 1 - это одно и то же дополнение).