Как изменился культовый онлайн-шутер и что осталось прежним
01.01.2011 —
дикозабр
задачка (программистское)
avva — 05.01.2011
Задачка для программистов и интересующихся. Наверняка известная, но
мне в такой форме не встречалась, и понравилась.Дан массив размером N, в нем есть только числа от 1 до N-1 (необязательно все, необязательно по порядку). Очевидно, какие-то из них повторяются. Найти какое-то число, которое встречается в массиве больше одного раза.
Суть в том, чтобы сделать это с как можно лучшей сложностью времени и места. Скажем, тривиально сделать это за O(N) времени с O(N) места. Можно лучше. Исходный массив не бесплатный: его можно менять, но это считается в бюджет места.
Сохранено
|
|
</> |
Оставить комментарий
Популярные посты:
Предыдущие записи блогера :
Архив записей в блогах:
1. Taobao — китайский интернет магазин сегодня находится на первом месте, в рейтинге самых популярных. 2. Интернет магазин китайской одежды LightInTheBox является не менее популярным ...
Что стану симпатизировать Арье Дери. Религиозному ортодоксу восточного разлива, одно время любимому ученику рава Овадьи Йосефа. Получившему исключительно религиозное образование, организатору партии ШАС, гонителю «русской» алии, да к тому же осуждённому за взятки, коррупцию, финансовые ...
Насколько я поняла, пробежавшись сегодня по ленте, что люди не понимают важного в сносе объектов в Москве. Они построили капитальные строения на арендованных землях, надеясь, что это навсегда. Им дали срок для того, чтоб они забрали свою собственность с чужой земли. Они не стали этого д ...
Во время акции автомобилистов в Минске задержан один человек Один человек был задержан вечером во вторник в Минске на акции протеста автолюбителей, которые выражали несогласие с очередным повышением цен на нефтепродукты. ...Сотрудники ОМОН ...
Тот, кто их туда послал или, как обычно, американский госдеп?.. Сирийские боевики не дали нам ни малейшего повода для того, чтобы мы начали их бомбить. Ни одного. Они никак не провоцировали нас на эту войну... А это неважно, - сердятся упоротые российские имперцы - Мы должны бомбить ...
