Есть 2 больших массива A[N] и B[M], в каждом из которых есть по одному одинаковому элементу, т.е. A[x] = B[y] 0 <= x < N 0 <= y < M необходимо найти x и y. Подскажите методы быстрого нахождения x и y. Полный перебор N*M категорически неприемлем... Может кто у Кнута встречал?
Либо сортировка, либо нужна доп. информация о размере массива и диапазоне значений элементов, может тогда что-то придумается
Имхо, поразрядная сортировка и дальнейший линейный поиск (сравнили A`[1] в B`[1], где вышло меньше, по тому массиву идём далее, пока не натыкаемся на бóльшее число, тогда меняем массив по которому ходим — ну и так далее, пока нет равенства). Или O(N+M) доп. памяти у нас тоже нет?
Элемент массива представляет собой объект длиной в n байт в общем случае (от 4 до 256), диапазон значений - любой, размеры массивов - по несколько миллионов элементов...
Вообщем, так пока и реализовал: -выделение памяти под массив C[N+M], копирование элементов из А,В в С - (N+M) -быстрая сортировка за - K1*(N+M)*log(N+M) -поиск в массиве C[N+M] двух одинаковых, рядом стоящих элементов - (N+M) -если элементы найдены в пред-м пункте, то поиск номеров x и y в A и B - (N+M) qqwe Если быстрее вышеописанного, то дайте ссылку, плиз.
какой-такой ссылки? разве не знать хэш таблицы? почему не хотеть читать про хэш таблицы в гугле? (абиделись? - лучше делайте как хотите)
Ну можно ещё конечно поюзать хеш и сделать такой вариант Код (Text): boolean flags[P] = {false}; for_each(x in A) { flags[hash(x)] = true; } for_each(y in B) { if (flags[hash(y)]) { for_each(x in A) { if(x=y) { printf "found element!"; } } } } Получается, что если условие 'if (flags[hash(y)])' будет не часто срабатывать, то поиск будет быстрым.... Значит, получается вариант с сортировкой оценивается как O((N+M)*log(N+M)), а с хешем как O(K*(N+M)), где K - количество срабатываний условия flags. Если K больше чем log(N+M), то вариант с сортировкой лучше, иначе лучше сортировка. Попытаемся оценить K. Будем считать, что вероятность срабатывания условия равна отношению количества true-элементов (TL) в массиве flags к общему количеству элементов(P) массива. Получается, что K=(TL/P)*N. Т.е. для того чтобы К был меньше чем log(N+M) нужно чтобы подавляющее большинство элементов из flag были false... ну если как-то возможно реализовать эти условия, то можно применить этот метод. Также не стоит забывать, что у варианта с сортировкой время будет всегда близко к NlogN, т.к. пока мы всё не отсортировали мы не можем начать искать, а во варианте с хешем, с шансами при первом же срабатывании условия flags будет найдено совпадение и поиск будет завершён.
А не выгоднее ли сортировать массивы по-отдельности, а уже потом прямо по отсортированным однопроходно одновременно пробегаться? ИМХО, N*log(N) + M*log(M) меньше, чем (N+M)*log(N+M). А однвременный пробег - по типу однопроходного поиска максимума, в каждом из массивов свой указатель, сдвигающийся к следующему элементу, если число по указателю в другом массиве больше i,i=0; while(i<N && j<M) { if(A>B[j])j++; else if(A<B[j])i++; else найдено } не найдено
