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

[yigal_s]

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

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

Comments

[vladiv.livejournal.com]

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