программизм: вот такая задачка образовалась

[yigal_s]

Дан массив из N элементнов. Ну, к примеру, integers
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.

Upd: дополнительное условие - не аллоцировать дополнительных массивов.

Comments

[igorbor.livejournal.com]

А что-нибудь еще про массив известно? уникальные ли в нем числа, в каком диапазоне, то, се? или в самом общем виде?

[yigal_s]

ну пусть уникальные. Диапазон произвольный (radix-sort побоку)

[igorbor.livejournal.com]

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

А в реальной жизни - сортировать :)

[oblomov-jerusal.livejournal.com]

Посчитать суммы двух, массивов, суммы квадратов, суммы кубов и суммы четвертых степеней. Разности дадут суммы удаленных элементов и их степеней. Получится система из четырех уравнений с четырьмя неизвестными. Если ֶa_1...a_4 наши неизвестные, то коэффициенты многочлена (t-a_1)(t-a_2)(t-a_3)(t-a_4) можно выразить через полученные суммы. Четыре корня многочлена и будут нашими неизвестными.

[yigal_s]

Точно.

В лоб

[dimrub.livejournal.com]

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

Re: В лоб

[yigal_s]

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

Re: В лоб

[dimrub.livejournal.com]

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

Re: В лоб

[igorbor.livejournal.com]

То есть Вы предполагаете, что обьем хеша будет меньше обьема массива? Это, по-моему, в общем случае неверно. А если обьем хеша мал, то цена поиска в нем будет не меньше, чем цена сортировки изначального массива.

Re: В лоб

[yigal_s]

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

Для смеха

[profi.livejournal.com]

Я не программист. Да и арифметику подзабыл. :-)

Просто, чтобы проверить себя. Если оба массива упорядочить по одному и тому же закону, а потом вычесть поэлементно. Все ненулевые значения в массиве разности - это удаленные. Да? Нет? Только не бейте сапогами по голове! :-)))))

Re: Для смеха

[dimrub.livejournal.com]

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

Re: Для смеха

[profi.livejournal.com]

Да, конечно. Я просто привык к софту типа Ориджин, в качестве пользователя. А вот о том, что там внутри работает - забываю.

ПС Да, забыл еще укороченный массив дополнить нулями. Чтобы матрицы (илив векторы) были одинаковых размерностей. Но это уже не актуально. :-)

Re: Для смеха

[haraz-bey.livejournal.com]

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

[yigal_s]

правильно. Но упорядочивать массивы - слишком долго.

[haraz-bey.livejournal.com]

Это да. Я имел в виду, что если сравнивать таким образом, то нужен сдвиг. Можно было бы проверить каждый элемент из первого массива на наличие во втором, но это действительно для двух любых массивов, значит, мы теряем преимущество, заключающееся в дополнительных данных, известных о конкретных массивах. А вот как его использовать - надо еще подумать :)

[dr-tambowsky.livejournal.com]

Упорядочивать долго, но если не пользоваться никаким упорядочиванием (или чем-то в данном контексте эквивалентным типа хэш-таблицы, как предлагалось выше), то, казалось бы, время должно быть О(N^2), что всяко ещё хуже. Разве не так?

[haraz-bey.livejournal.com]

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

[vladiv.livejournal.com]

Отсортирован ли исходный массив? Если нет, отсортировать бинарной сортировкой. Второй массив (копию) отсортировать в любом случае. Дальше двигаться последовательно по первому массиву (i). сравнивая его с копией (j=i). Несравнение по некоторому индексу (i) означает, что этот элемент, выброшен из второго массива. Нарастить i и продолжать сравнение.
Лучшего алгоритма я пока не вижу, но, возможно, он есть.

[occuserpens.livejournal.com]

Отсортировать оба массива на месте и сравнить

[occuserpens.livejournal.com]

Это единственно разумное программистское решение. Придумывать какие-либо оптимизации этого способа - это теория, которая к практике никакого отношения не имеет.

[thornik.livejournal.com]

А вы специально указали "integers", чтобы притянуть задачу к арифметической или вас интересовал алгоритм со, скажем, строками?