добрый день

помогите с алгоритмом.

задача.

есть два неупорядоченных массива a и b. 
b отличается тем что в нем отсутствует 2 элемента, (т.е их удалили) 
наиболее оптимальным методом найти эти два элемента.

Пример.
1 4 5 2 6 7 3 10
1 5 6 7 2 3 

10 и 4

отсортируйте один из массивов
берите по очереди элементы из второго массива и ищите их в первом, если нашли, то вычеркивайте из первого

Какие имеются ограничения на элементы массива?

Думаю довольно неплохим тут будет следующий алгоритм.

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

1 4 5 2 6 7 3 10 {1 массив}
1 5 6 7 2 3        {2 массив}

1 2 3 4 5 6 7 10 {1 отсортированный массив}
1 2 3 5 6 7        {2 отсортированный массив}

Пусть полный массив это A, неполный - B, дальше смотрим:

A[1]=B[1], все норм, совпадают
A[2]=B[2], тоже
A[3]=B[3], тоже
A[4]!=B[4], а вот тут нет, элемент неполного массива не совпадает => отсутствует элемент, равный A[4], т.е. четверка. И тут либо вставляем этот элемент в неполный массив и продолжаем, либо убираем этот элемент из полного массива.

Ну и так далее. Извини за много букв, люблю все разжевывать до мелочей.

Это сообщение отредактировал(а) Zmaster555 - 28.2.2013, 16:02

сложность алгоритма o(n) + m  и можно использовать дополнительную память только для одной переменной

knut, повторяю

Могут они быть отрицательными? дробными? тысячезначными? повторяющимися? 

Akina, натуральные положительные числа ,нет они не повторяются.
спасибо.

knut, ты способен отвечать на вопрос ПОЛНО? Есть ли верхняя граница? или, просмотрев весь список, можно в конце обнаружить число из миллиона цифр?

Akina, 



нет

  
число не одно а два. да можно обнаружить в конце.

Ок.

Первый проход. Находим самое большое число.
Второй проход. Зная диапазон, XORим числа обоих списков общим потоком, используя память для одной переменной. Результат равен XORу двух отсутствующих во втором списке чисел.
Как действовать дальше, не имея доп. памяти, пока не придумал.

knut, 

Не получиться такой список не поместиться в память компьютера.
Да тут даже одно число не влезет в память компьютера. Так что пока вы не сделаете реального условия вы не получите реального ответа.

Добавлено через 1 минуту и 42 секунды
Akina, 
По моему автор путает цифры с числами.

На такие мелочи я не стал обращать внимание... в его словах всё ещё несколько нестыковок и нелепиц...

за O(n) проходов можно решить c 2-мя переменными (достаточной точности.)

S = 0;
P = 1;

for (i = 0; i < size; ++ i)
{  S += first [i] - second [i];
   P *= first [i] / second [i];
}

пробегаем весь массив.
В результате имеет сумму и произведение двух оставшихся неизвестных чисел. 

решить  элементарное уравнение

x + y = S
x * y = P

труда, думаю уже не составит.  

volatile, классная идея
только не хватает пары if, т.к. размеры массивов разные

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