Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
26.11.2010, 17:44
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Добрый день, всем! Есть задачка: Есть список номеров угнанных машин по городу и есть список номеров машин за сегодня, которые проехали по городу. Нужно получить список номеров уганных машин, которые проехали по городу за сегодня. Нужно найти алгоритм, при этом он должен быть линейной сложности(не должно быть вложенных циклов). Есть идеи? Заранее спасибо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 17:58
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
truel, а номера какого вида? обычные российские? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:03
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Яростный Меча номера какого вида? обычные российские? Дык не пофигу ли? Сравнение на тупое равенство наверняка. Афтар, видимо, интересуется только цикловой строной вопроса. Оба списка сортируются, потом одновременный односторонний проход по обоим. Merge join , иными словами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:04
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
GSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:11
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
Яростный МечGSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность. Тогда отсортированность списков вменяем в исходные условия ))) А то об этом же ни слова. Кто сказал, что они не отсортированы изначально? ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:12
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Яростный МечТребуется линейная сложность. Да, но ввиду уточняющей фразы автора "не должно быть вложенных циклов" мне представляется, что автор, не до конца разбираясь в тонкостях момента, имел в виду "не N^2", а не "обязательно N". Также представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:19
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
GSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет. Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:26
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
GSergЯростный МечТребуется линейная сложность. Да, но ввиду уточняющей фразы автора "не должно быть вложенных циклов" мне представляется, что автор, не до конца разбираясь в тонкостях момента, имел в виду "не N^2", а не "обязательно N". Вопрос был с собеседования, насколько помню требовалось найти именно линейную сложность. Списки неотсортированы. Поэтому Merge join, как я понимаю, не годится, т.к. нету алгоритма сортировки с сложностью менее n*log(n). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:29
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
Яростный МечGSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет. Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь Там задачка "немного" другая. А тут - есть массивы (пусть с целыми числами - это абсолютно ничего не даст): [5, 6, 1, 10, 3, 4, 19] [32, 2, 4, 8, 1, 11, 7, 13] Ну как ты в один проход линейно найдешь пересечение этих двух массивов? Никак. Только если они изначально упорядочены. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:31
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Яростный МечGSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет. Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь Почитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:39
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
truelПочитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись. Замени набор букв и цифр на числа. Это поможет? Нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:42
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Edd.DragontruelПочитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись. Замени набор букв и цифр на числа. Это поможет? Нет. Не понимаю, как это может помочь. Пусть будет алгоритм кодирования номера в число и обратный алгоритм декодирования, и мы имеем тогда дело только с числами. В том примере нужно было только один выкинутый номер, а здесь не просто номер, а серию номеров. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 18:57
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
truelНе понимаю, как это может помочь. Пусть будет алгоритм кодирования номера в число и обратный алгоритм декодирования, и мы имеем тогда дело только с числами. В том примере нужно было только один выкинутый номер, а здесь не просто номер, а серию номеров. Так я так и сказал - НЕ поможет. Можно забыть о той задаче и не мусолить ее в мозгу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 19:04
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Можно ли задачу решить так: 1. хэшируем 1 массив всех номеров города. 2. ищем каждый элемент 2 массива в хэш-таблице 1 массива. Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 19:08
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
truelМожно ли задачу решить так: 1. хэшируем 1 массив всех номеров города. 2. ищем каждый элемент 2 массива в хэш-таблице 1 массива. Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)).в принципе так можно и за линейное время уложиться, но для этого надо хэш примерно на 35937000 персон. Что там с ограничением по памяти? Да и предварительно обнулить элементы придется... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 19:10
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
хотя нет, многовато. 4492125 байт понадобится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 19:13
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
truelМожно ли задачу решить так: 1. хэшируем 1 массив всех номеров города. 2. ищем каждый элемент 2 массива в хэш-таблице 1 массива. Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)). Тогда фраза "не должно быть вложенных циклов" отпадает. Цикл по второму массиву { Цикл-поиск в таблице хешей } ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 21:53
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
Яростный Меч, В автомобильных номерах используются далеко не все буквы кириллицы, так что возможных номеров меньше. С другой стороны, есть ещё код региона... А необходимость обнулять табличку добавляет константное время и не влияет на асимптотику, так что требования формально соблюдены. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 21:59
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
select можно использовать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.11.2010, 22:54
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
две таблички, индексы, джойн :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
27.11.2010, 00:57
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
Яростный МечGSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность. А в этом случае какова сложность будет? Разве не N? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
27.11.2010, 01:56
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Народ, вы чего? Поскольку ограничения на ресурсы не указано, задача решается элементарно - составлением матрицы (решета). Edd.Dragon и ЯрМеч были правы, смысл примерно таков и есть. Давайте посчитаем ( http://gibdd.net/codes.html) - на данный момент мы имеем всего 10*10*10*12*12*12*122=210816000 федеральных автономеров. Для их запоминания (есть-нет) достаточно массива (матрицы) объемом 26352000 байт (т.е. всего ~25 МБайт). Даже с учетом номеров спецтранспорта и т.п. возрастает он ненамного. Таким образом, алгоритм прост: - описываем функцию, позволяющие сопоставить конкретный номер с его местом в матрице - инициализируем матрицу - проходим 1 раз по массиву "проехавших авто" и отмечаем их в матрице - проходим 1 раз по массиву "угнанных авто", преобразуем номер в место и сверяем с матрицей, в случае совпадения - запоминаем. Усё... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
27.11.2010, 10:02
|
|||
|---|---|---|---|
|
|||
задачка |
|||
|
#18+
AndreTM, А составление матрицы какую сложность имеет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
27.11.2010, 10:04
|
|||
|---|---|---|---|
задачка |
|||
|
#18+
Edd.DragonAndreTM, А составление матрицы какую сложность имеет? Никакую. Поскольку заранее создаём массив нужного размера. Простое выделение памяти... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&tablet=1&tid=1343300]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
199ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
51ms |
get tp. blocked users: |
1ms |
| others: | 239ms |
| total: | 531ms |
| 0 / 0 |
