Найти удаленное число

wanderer · Чт дек 27, 2001 4:28 pm

Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

Подсказка - как это можно было бы ЗАПРОГРАММИРОВАТЬ?

[ 27-12-2001: Message edited by: wanderer ]

Andy77 · Чт дек 27, 2001 5:05 pm

<blockquote>:<hr>Originally posted by wanderer:
Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>
методом деления пополам? [img:bd4ba1b278]images/smiles/icon_confused.gif[/img:bd4ba1b278]

Andy77 · Чт дек 27, 2001 5:10 pm

а если массив Y после удаления элемента еще и перемешали, то получается линейная сложность, если допустить, что мы можем использовать кусок памяти размером MAX(X) [img:3d70f54aed]images/smiles/icon_wink.gif[/img:3d70f54aed]

Kisena · Чт дек 27, 2001 5:10 pm

<blockquote>quote:<hr>Originally posted by Andy77:
<blockquote>:<hr>Originally posted by wanderer:
[qb]Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>
методом деления пополам? [img:fbe19d8891]images/smiles/icon_confused.gif[/img:fbe19d8891] [/QB]<hr></blockquote>

Если в массиве одно и то же число может появляться несколько раз, то не очень понятно, как реализовывать метод деления пополам.

Andy77 · Чт дек 27, 2001 5:20 pm

<blockquote>quote:<hr>Originally posted by Kisena:


Если в массиве одно и то же число может появляться несколько раз, то не очень понятно, как реализовывать метод деления пополам.<hr></blockquote>

точно так же как и в случае с уникальными числами... делим отрезок пополам, пока не наткнемся на
[b:8930d7f0db]n : X[n]!=Y[n]&& X[n-1]==Y[n-1][/b:8930d7f0db]

[ 27-12-2001: Message edited by: Andy77 ]

Drom · Сообщение **Drom** » Чт дек 27, 2001 5:42 pm

<blockquote>quote:<hr>Originally posted by Andy77:
а если массив Y после удаления элемента еще и перемешали, то получается линейная сложность, если допустить, что мы можем использовать кусок памяти размером MAX(X) [img:2f0bbdded9]images/smiles/icon_wink.gif[/img:2f0bbdded9] <hr></blockquote>

наверное, это и имелось в виду. в остальных случаях проще найти число _вместе_ с его индексом.

wanderer?

wanderer · Чт дек 27, 2001 6:42 pm

Поскольку не сказано что числа все разные, то ... хмм ... они могут быть одинаковы. Поэтому, вопрос о положении удаленного элемента в общем случае неразрешим. Ну разве что попросить положение КАКОГО НИБУДЬ элемента с тем же значением. Но и этого не спрашивается. Все что спрашивается, это какое ЧИСЛО было удалено, где бы оно не находилось.

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

[ 27-12-2001: Message edited by: wanderer ]

Andy77 · Чт дек 27, 2001 8:46 pm

<blockquote>quote:<hr>Originally posted by wanderer:
Поскольку не сказано что числа все разные, то ... хмм ... они могут быть одинаковы. Поэтому, вопрос о положении удаленного элемента в общем случае неразрешим. Ну разве что попросить положение КАКОГО НИБУДЬ элемента с тем же значением. Но и этого не спрашивается. Все что спрашивается, это какое ЧИСЛО было удалено, где бы оно не находилось.

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

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>

Тогда считаем суммы первого и второго массива - сойдёт?

Chapaev · Чт дек 27, 2001 8:51 pm

<blockquote>quote:<hr>Originally posted by wanderer:
Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

Подсказка - как это можно было бы ЗАПРОГРАММИРОВАТЬ?<hr></blockquote>

Я бы отсортировал оба массива X и Y функцией qsort. А затем
for(int i=0; i<N-1; i++)
if(X[i] != Y[i])
return X[i];
return X[N-1];

Chapaev · Чт дек 27, 2001 8:55 pm

<blockquote>quote:<hr>Originally posted by Andy77:


Тогда считаем суммы первого и второго массива - сойдёт?<hr></blockquote>

Просто и красиво!

Drom · Сообщение **Drom** » Чт дек 27, 2001 9:00 pm

<blockquote>quote:<hr>Originally posted by Chapaev:

Я бы отсортировал оба массива X и Y функцией qsort. А затем...<hr></blockquote>

сложность у quicksort'а (что нас в этой задаче и заботит) N * log(N) - больше чем линейная.

wanderer · Чт дек 27, 2001 9:34 pm

<blockquote>quote:<hr>Originally posted by Andy77:


Тогда считаем суммы первого и второго массива - сойдёт?<hr></blockquote>

Для математика сойдет вполне [img:430f246ab8]images/smiles/icon_smile.gif[/img:430f246ab8] И действительно, просто и красиво.

Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:430f246ab8]images/smiles/icon_sad.gif[/img:430f246ab8]

Тогда как ?

Kisena · Чт дек 27, 2001 9:42 pm

А сравнивать можно? Насколько мы помним, сравнение двух чисел производится путем сравнения их разницы с нулем. Или теперь так не делают? Или никогда так не делали?

Drom · Сообщение **Drom** » Чт дек 27, 2001 9:44 pm

<blockquote>quote:<hr>Originally posted by wanderer:
Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:45b8d2a598]images/smiles/icon_sad.gif[/img:45b8d2a598]

Тогда как ?<hr></blockquote>

недобрый Вы, Wanderer [img:45b8d2a598]images/smiles/icon_sad.gif[/img:45b8d2a598] [img:45b8d2a598]images/smiles/icon_mad.gif[/img:45b8d2a598] [img:45b8d2a598]images/smiles/icon_wink.gif[/img:45b8d2a598]

XOR!

[ 27-12-2001: Message edited by: Drom ]

sttranik · Чт дек 27, 2001 9:58 pm

<blockquote>quote:<hr>Originally posted by wanderer:
Для математика сойдет вполне [img:06aa4e0c2d]images/smiles/icon_smile.gif[/img:06aa4e0c2d] И действительно, просто и красиво.

Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:06aa4e0c2d]images/smiles/icon_sad.gif[/img:06aa4e0c2d]

Тогда как ?<hr></blockquote>
сложение в поле ? то что по программистки называется wrap around ?

теперь давайте усложним задачу. скажем что во втором массиве меньше не на одно а на два числа. как найти эти два числа?

PS. Между прочим мне эту задачу задавали на интервью [img:06aa4e0c2d]images/smiles/icon_smile.gif[/img:06aa4e0c2d]