добрый день

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

задача.

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

Вот только что промоделировал на случайном массиве из 64к элементов в пределах unsigned long.
Если вычисления проводить в double - ну более-менее, хотя один расчёт из двадцати дал ошибку на единицу (102201990, расчётно 102201989).
Счас попробую в single (он, как и ulong, 4 байта)... боюсь, будет грустно.

Это сообщение отредактировал(а) Akina - 1.3.2013, 09:11

Один расчёт из 10 дал ошибку - 17123904, расчётно 17123903...

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

1*1+8*8=4*4+7*7=65
аналогично с кубами 
1*1*1+12*12*12=9*9*9+10*10*10=1729
То же и с остальными степенями... не пойдёть.

то, что квадраты требуют больше места, чем числа - ожидаемо

просто, если среди чисел нет уж очень большого неравенства (типа, одно огромное, а остальные маленькие), то в случае с квадратами результирующее число будет меньше

понятно, что это уже использует какие-то предположения о числах...

о...

если предположить, что в дополнительных переменных у нас достаточно бит для хранения любого числа из массива, то можно найти числа по половинкам:
1. сначала рассматриваем младшую половину бит каждого элемента, считаем для них суммы и суммы квадратов - всё поместится, находим пару младших половинок
2. то же самое для старших - находим пару старших половинок

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

а точнее, 
переменная P Должна быть в 2 раза длиннее чем типы массива.
переменная S Должна иметь на 1 бит больше чем типы массива.

Тогда решаецца строго, для любых данных. (при аккуратном программировании).

double не подойдет для 32 разрядов, так как там 56 бит (если не ошибаюсь.) а нужно 64 битов мантисы.
float тем более.

long double в gcc, должен подойти.  long double у M$ не пойдёт.
Ну или делать как предлагает maxim1000, длинную арифметику вручную.