Оптимальный способ найти, повторяется ли какой-либо элемент в данном массиве?

Question

Каков наилучший оптимальный способ определить, повторяется ли какой-либо элемент в данном массиве?

Answer 1

Поместите элементы в хеш-таблицу, выполняя сравнения на равенство значений при любых коллизиях.

Answer 2

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

Еще один способ сделать это, не используя хеш-таблицы. Просто отсортируйте массив (используя qsort) и переберите элементы, проверяя, совпадают ли два соседних элемента. Сортировка позволяет группировать одни и те же элементы, что упрощает проверку на наличие дубликатов. Конечно, это O (nlog) и изменит порядок исходного массива, но он намного короче и избавляет вас от необходимости кодировать хеш-таблицу.

Answer 3

Если мы считаем, что дубликатов может быть больше двух для случая, подобного: {2,3,2,2,2,5,5,7,7}, здесь нам нужно создать хеш-таблицу, а затем искать без дубликатов

Использование контейнера карты STL становится очень простой задачей: (Вопрос не был помечен для C ++, но STL сделает задачу хеширования чистой). Он также может обрабатывать случаи во всех уникальных случаях.

  #include <iostream>
  #include <vector>
  #include <iterator>
  #include <map>
  using namespace std;

 int main(void){
      map<int,int> array;
      map<int,int>::iterator ii;

    int arr[] = {2,3,5};
    vector<int> unique_list;
    int size = sizeof(arr)/sizeof(arr[0]);

    for(int i = 0; i<size; i++)
          ++array[arr[i]];

     bool flag = false;

    for(ii=array.begin();ii != array.end(); ++ii)
     if(ii->second == 1){
         flag = true;
         unique_list.push_back(ii -> first);
       }

   if(flag == true){
      cout<<"Unique element(s): ";
      copy(unique_list.begin(),unique_list.end(),ostream_iterator<int>(cout," "));
     }
   else
     cout<<"All elements have dulicate"<<endl;

   return 0;
 }

Сложность O (n), поэтому она все еще в линейном времени.

Answer 4

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

Answer 5

Может быть не то решение, которое вы ищете, но:

• если элементы являются целыми числами
• , а если , вы знаете их максимально возможное значение MAX,

построить массив DUPS размера [MAX], где каждый элемент равен нулю; разбирать исходный массив ORIG и для каждого элемента i:

int i;
for ( i = 0 ; i < DUPS_SIZE ; i++ )
    if ( DUPS[ORIG[i]] == 1 ) 
        return true; /* the original array has duplicate elements */
    else
        DUPS[ORIG] = 1;
return false;

Или вы можете перебирать ORIG в случайном порядке. Худший случай - все еще O (DUPS_SIZE).

Answer 6

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