Найти дубликаты в массиве в O (N) времени

Ответ 1

Я считаю, что хорошее решение (приличное использование памяти, может быть использовано для немедленного определения, если запись уже была замечена, сохраняя порядок и с линейной сложностью) trie.

Если вы вставляете элементы в trie, как если бы они были строкой с каждой цифрой (начиная с MSD) в каждом node, вы можете снять это со сложностью O (m N), где m является средняя длина чисел в десятизначных числах.

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

Я не уверен, что вам будет полезно использовать здесь суффикс-дерево, поскольку "базовая" символов, вводимых в trie, равна только 10 (по сравнению с базой-128 для строк ANSI), но это возможно.

Ответ 2

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

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

Ответ 3

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

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

Создайте хеш-таблицу, которая сопоставляет элементы массива двум битам в качестве поля подсчета от нуля до трех и тридцать битов в качестве индекса в массиве элементов. Если вы не получили более миллиарда значений в вашем массиве, достаточно тридцать бит. Таким образом, ваши значения хэша - это всего лишь одно 32-битное слово.

Пройдите элементы в массиве. Если элемент отсутствует в таблице, вставьте это значение в хэш-таблицу и установите для поля count значение 0. Неважно, какая часть индекса находится при его хранении. Если элемент находится в таблице, а поле счетчика равно нулю, увеличьте его до 1 и сохраните индекс элемента с новым значением поля счета. Если поле count уже одно или больше, установите его на два и не касайтесь сохраненного индекса - оставьте его как есть.

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

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

Ответ 4

Если вы знаете максимальное значение, которое вы можете сделать так, имеют отдельный массив с длиной как максимальное значение

 int[max] secondarray;

    for(int i=o;i<arrayFirst.length;i++){
        if(secondarray[arrayFirst[i]]==0){
            secondarray[arrayFirst[i]]==arrayFirst[i];
         }else{
             result.add(arrayFirst[i]);
          }
     }

Ответ 5

Вы можете сделать это в O (n), это потребует, чтобы массив был целым. Требуемое пространство для этого может быть размером порядка -2 ^ 32 до 2 ^ 32. Вам нужно будет найти max и min исходного массива (arrayorig). Затем создайте два массива (arraynew +) и (arraynew-).

Размер (arraynew +) будет max (arraorig) -min (arrayorig), если все значения в arrayorig равны +, иначе размер (arraynew +) будет max (arrayorig).

Размер (arraynew-) будет равен нулю, если все значения будут положительными, иначе они будут равны абсолютному значению min (arrayorig).

Затем вы можете выполнить итерацию по arrayorig и увеличить значение на 1 of (arraynew-) или (arraynew +) в индексе, соответствующем значению arraorig, если значение равно положительному приращению, нужно сделать (arraynew +) else if его отрицательное приращение должно быть сделано до (arraynew-) по индексу (arraynew-), который равен абсолютной величине arrayorig. Тогда все индексы (arraynew +) и ((arraynew-) со значением > 1 являются отдельными значениями arrayorig.

Ответ 6

 void printRepeating(int arr[], int size)
 {
 int i;
   printf("The repeating elements are: \n");
 for (i = 0; i < size; i++)
 {
 if (arr[abs(arr[i])] >= 0)
  arr[abs(arr[i])] = -arr[abs(arr[i])];
 else
  printf(" %d ", abs(arr[i]));
 }
  }

Ответ 7

Найти дубликаты так же сложно, как и сортировка. Лучше всего использовать какое-либо свойство вашего ввода, чтобы получить сортировку O (N).