воскресенье, 26 октября 2008 г.

Поиск дубликатов в массиве

Задача

Есть массив целых от 1 до N. Нужно определить, есть ли в этом массиве повторяющиеся значения.

Решение

Задачу можно решить несколькими способами. Первое, что приходит в голову - отсортировать исходный массив и сравнивать соседние элементы. Затраты по времени и по расходуемой памяти будут зависеть от алгоритма сортировки, например, при быстрой сортировке временная сложность будет O(nlogn +n-1) и емкостная сложность (память) будет O(logn).


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

// исходный массив, со значениями от 1 до 9
src_array = [1,3,8,4,2,9,3,9]

// дополнительный массив на 9 элементов (что бы уместились от 1 до 9)
add_array = [0,0,0,0,0,0,0,0,0]

// после обработки исходного массива результирующий будет выглядеть так:
// одна единица, одна двойка, две тройки, одна четверка, одна восьмерка и две девятки
add_array = [1,1,2,1,0,0,0,1,2]


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

Вывод

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

11 комментариев:

Анонимный комментирует...

использовать 2й вариант, только вместо массива использовать хеш (он же: map, ассоциативный массив).

Анонимный комментирует...

Как вариант, в реализации быстрой сортировки при сравнении значений ячеек, если они равны писать значение ячейки в дополнительный массив...

Lazin комментирует...

Можно сделать за линейное время и без ограничений, если использовать к примеру boost::unordered_map, вместо массива.
К тому-же этот алгоритм легко распараллелить :)

sash_ko комментирует...

2Анонимный: да, использование хеша - хорошее решение, позволяющее не привязываться к типу данных исходного массива.
А вот делать свою реализацию модифицированной быстрой сортировки лень :)

sash_ko комментирует...

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

Lazin комментирует...

Для того, что-бы распараллелить, достаточно разделить массив на N частей и обработать каждую часть в своем потоке. Если использовать lock free хэш, вместо boost::unordered_map, то будет работать в N раз быстрее :)

Ray комментирует...

Гляньте еще алгоритм Флойда http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare

Анонимный комментирует...

Если пользоваться стандартными возможностями языка, то на Python'е это можно записать так:
# создаем список (который, в отличие от обычного массива можно заполнить любыми данными)
lst = ['a',1,2,3,5.7,3,'a',2,4,5,1,5.7,1,1]
# создаем другой список, в который помещаем все элементы списка lst, встречающиеся более одного раза
a = [i for i in lst if lst.count(i) > 1]
# если такие элементы нашлись, возвращаем список a
if len(a) > 0: print a
В данном случае результатом будет:
['a', 1, 2, 3, 5.7, 3, 'a', 2, 1, 5.7, 1, 1]
Пример простой, но для решения задачи, думаю, сгодится. :-)

sash_ko комментирует...

сгодится, только если не будет ограничений по скорости - для каждого элемента список будет обрабатываться заново, это равносильно вложенному циклу:

for item in lst:
count = 0
for sitem in lst:
if sitem==item:
count+=1

AzusDex AZ комментирует...

а если есть огромный массив 1000000 чисел, и нужно найти два первых одинаковых числа, сортировкой пользоватся нельзя, дополнительный массив создать можно, но только размером 5, и так же o(n)?

Николай комментирует...

На PHP так пока только придумал:

// Генерируем
$MAX = 1000000;
$arr = []; $count = $MAX;
while( $count -- ) {
$arr [] = rand( 100000, 1500000);
}

// Находим
$tm = microtime( true );
$doubles = []; $temp = [];
foreach( $arr as $val ) {
if( ! isset( $temp [ $val ])) {
$temp [ $val ] = 1;
} elseif( ! isset( $doubles [ $val ])) {
$doubles [ $val ] = 1;
}
}
$doublesCountTime = microtime( true ) - $tm;
$doublesCount = count( $doubles);
$doubles = array_keys( $doubles );

В php isset( $a [$k]) работает быстрее чем in_array( $k, $a)

Ищу что побыстрее )))