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

[yigal_s]

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

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

Comments

[igorbor.livejournal.com]

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

[oblomov-jerusal.livejournal.com]

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

В лоб

[dimrub.livejournal.com]

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

Для смеха

[profi.livejournal.com]

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

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

[vladiv.livejournal.com]

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

[occuserpens.livejournal.com]

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

[thornik.livejournal.com]

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