Как найти, какой элемент был удален в массиве?

Question

[rocknow]

Простая задачка, на которую я тем не менее не смог ответить. Есть массив интов или байтов, мы в нем удаляем какой-то элемент путем формирования нового массива без этого элемента. Массивы неотсортированы. Как имея эти 2 массива, узнать, какой элемент был удален? Естественно, без перебора, нужно наиболее эффективное/быстрое решение.
Задача общая, но если брать контекст языка, то берем java. Может есть какие-то стандартные методы, о которых я не знал.

Answer 1

[0xC0CAC01A]

Половинным делением. O(log N)

Comments

[Viktor Koltcov]

По условию, массив не отсортирован, для половинного деления надо будет сортировать а это уже как минимум O(n log n).

Расскажите как тут применить половинное деление?

[0xC0CAC01A]

Сортировка не нужна. Вам надо найти точку, где элемены ваших массивов с одинаковым индексом перестанут совпадать. Слева они совпадают, справа - нет. Кстати, не всегда возможно получить точный результат, например 1111111111111111111111111

Answer 2

[mamkaololosha]

В момент формирования запоминать значение или индекс удаленного элемента

Comments

[rocknow]

Ну я думаю имелся в виду точно не этот случай. Звучит ведь "как имея 2 массива". Про запоминание другого - ни слова. Хотя это тоже как вариант, спасибо.