Самый быстрый способ найти дубликат в массиве

Меня спросили в интервью, какой самый короткий или быстрый способ найти дубликат в массиве n элементов, которые могут быть целыми или поплавками. Хотя при поиске в переполнении стека есть решение, в частности, с использованием python, но если бы я хотел реализовать то же самое на некоторых языках программирования, таких как C или C++, какой алгоритм я могу использовать или есть ли способ, которым я мог бы это сделать в O (Н)?Самый быстрый способ найти дубликат в массиве

источник

2015-03-08 Trilok M

Самый быстрый способ, который я могу сделать, - сделать один проход, бросив каждый элемент в кучу и проверив, как вы идете. Это будет N * log (N) – stark

Дубликат или все дубликаты? –

один ... но я хочу, как это сделать для всех ... –

Хотя это может быть не самый эффективный с точки зрения пространства алгоритм, вы можете использовать хэш-карту для хранения каждого значения (ключа), с которым вы столкнулись при перемещении массива. Затем для каждого шага по вашему массиву вы будете выполнять поиск O (1) в своей хеш-таблице, чтобы увидеть, видели ли вы это значение раньше. Это решение - O (N), потому что вы перемещаете массив размера N только один раз, и на каждом шаге вы выполняете поиск хэша O (1).

Вот метод в C++, который реализует это:

#include <map> 

bool hasDupicate(int* input, int size) { 
    std::map<int, int> m; 
    for (int i=0; i < size; ++i) { 
    if (m.find(input[i]) != m.end()) { 
     return true; 
    } else { 
     // record the element you just saw in the map 
     m.insert(std::pair<int, int>(input[i], 1)); 
    } 
    } 

    // could not find any duplicate 
    return false; 
}

источник

2015-03-08 15:31:24

Большинство языков поддерживают также структуру данных HashSet. Кроме того, в качестве небольшой детали амортизированный поиск O (1) предполагает, что элементы хэшируются в ведрах «хорошо». Большинство API-интерфейсов позволяют дать начальную оценку размера/размера, чтобы убедиться, что поиск равен O (1). – uberwach

@Tim будет программа займет много времени, чтобы сохранить данный массив снова в hashmap? –

И теперь, в качестве эксперимента, попробуйте сравнить производительность этой проверки на основе карты с простой реализацией, которая просто: a) сортирует массив на месте b) проверяет смежные элементы, равные Во многих случаях во многих случаях накладные расходы создания элементов хэш-карты (особенно для std :: map, которая действительно является деревом RB) будет доминировать над затратами, а простая сортировка и проверка (хотя и асимптотически хуже) будут иметь лучшую производительность. – Krystian

Поскольку Тим спросил о решении с сортировкой, здесь

bool hasDuplicate(std::vector<int> & input) 
{ 
    std::sort(input.begin(), input.end()); 
    return std::adjacent_find(input.begin(), input.end()) != input.end(); 
} 

int main() { 
    std::vector<int> A { 2, 4, 9, 3, 8, 4, 5, 1 }; 
    std::cout << hasDuplicate(A) ? "has duplicates" : "no duplicates"; 
    return 0; 
}

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

источник

2015-03-08 18:18:55 Krystian

Самый быстрый способ найти дубликат в массиве

ответ

Смежные вопросы