?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [июл. 12, 2004|04:24 am]
Anatoly Vorobey
Хорошая программистская задачка:

Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).

Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.

P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: flashkot
2004-07-11 06:30 pm
можно ли модифицировать список данных (сортировать)?
(Ответить) (Thread)
[User Picture]From: avva
2004-07-11 06:36 pm
Всё равно ведь невозможно отсортировать за линейное время.
Но в принципе в условии задачи не сказано, можно ли модифицировать список. Ясно, что лучше обойтись без модификации, но я не скажу, можно без неё обойтись или нельзя ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alll
2004-07-11 06:44 pm
Нельзя ли уточнить, что значит "без дополнительной памяти. (кроме константы)." Константным подразумевается число дополнительных переменных или ничем кроме исходного массива и некоей константы нельзя пользоваться? Или нечто иное?
(Ответить) (Thread)
[User Picture]From: avva
2004-07-11 06:47 pm
Размер дополнительной памяти, которой можно пользоваться - константа, т.е. не зависит от размера исходного списка. Это может быть какое-то фиксированное число дополнительных переменных, или дополнительный массив фиксированного размера, итп.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dmitryle
2004-07-11 07:21 pm
Если такое число существует, то оно median (как оно по-русски называется?). Говорят (в сети), что есть линейный метод нахождения median. Находим (за линейное время) и проверяем (также за линейное время).
(Ответить) (Thread)
[User Picture]From: avva
2004-07-11 07:33 pm
Остроумно! ;-)

Но требует дополнительной памяти, линейной от размера исходного списка (для хранения промежуточных данных во время рекурсивных вызовов алгоритма для нахождения медианы).
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: french_man
2004-07-11 07:27 pm
Сумма квадратична, извините.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alll
2004-07-11 07:52 pm
Еще уточнение, если не затруднит: для элементов списка существуют операции "больше"/"меньше"? или только "равно"?
(Ответить) (Thread)
[User Picture]From: avva
2004-07-11 08:35 pm
Можно делать больше/меньше при желании.
(Ответить) (Parent) (Thread)
[User Picture]From: dyak
2004-07-11 08:02 pm
Для четного количества в списке.
Если разделить список на пары, то если член "х" –– большинство, то, если искомый член "х" есть, то, если пары, где члены разные, повыкидывать, то
число пар, где оба члена –– "х" должно быть больше, чем число пар, где оба члена –– "не х". Как предельный случай можно поиграть со списком их а+1 белых и а–1 черных.

Значит действуем так: игнорируем все смешанные пары и ставим счетчик на 0. Идем до первой одинаковой пары, замечаем ее члены как кандидата на большинство, ставим счетчик на 1. Если следующая одинаковая пара такая же, то увеличиваем счетчик на 1, если она другая, вычитаем из счетчика 1. Если счетчик оказывается на 0, то следующая одинаковая пара дает нам кандидата и 1 в счетчике.

В процессе узнаем сколько членов в списке.

Если в конце процесса имеем не 0 в счетчике и кандидата, то на следующем прогоне считаем сколько найдем кандидата в списке. Если >50%, ура.

На нечетное число членов тривиально распространимо, но писать лень.
(Ответить) (Thread)
[User Picture]From: alll
2004-07-11 08:20 pm
А сколько потребуется "прогонов" в самом худшем случае?
(Ответить) (Parent) (Thread) (Развернуть)
From: ex_ilyavinar899
2004-07-11 10:22 pm
Я намеренно не смотрю на остальные комментарии.

Одно слово: хэширование.
(Ответить) (Thread)
[User Picture]From: dmitryle
2004-07-11 10:46 pm
Hash is not deterministic - what if all the values are in the same bucket?
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2004-07-12 01:14 am
Если на элементах задана операция сравнения и разрешается переупорядочивать список, то легко модифицировать стандартный алгоритм поиска элемента. Выбираем случайный элемент a, проходим по списку, составляем 2 списка: больших a и меньших или равных a. Выбираем больший из двух списков и продолжаем с ним работать. Если хотим детерминистский алгоритм, то из каждых 5 элементов выбираем медианный, находим медиану всех выбранных, и найденный элемент используем как a(OK, это уже не постоянная память)
(Ответить) (Thread)
From: oblomov_jerusal
2004-07-12 01:44 am
Пусть элемент представлен строкой в k бит. Проходим по списку, считаем, сколько раз встречается старший бит 0. Выбираем тот, что встречается чаще. На шагу i мы имеем i-1 старших бит элемента, и мы проходим по списку и считаем, сколько раз встречается 0 и 1 после этих i-1 бит, и определяем на основе подсчета бит i. (естественно, вместо бита можем пользоваться более крупной единицей, напр. байтом).
(Ответить) (Thread)
[User Picture]From: avva
2004-07-12 03:09 am
Да, так тоже можно.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2004-07-12 04:22 am

Nemnogo drugoe reshenie. Nabrosok idei

2 prohoda vdol' spiska.
Voz'mem nebol'shoj massiv (naprimer 10 elementov). Kazhdyj element massiva - para: element-chastota elementa. Budem zapisyvat' v nego elementi po mere postuplenia a zaodno i schitat' ih kolichestvo (chastotu). Kak tol'ko nam vstretit'sja 11-i element, nachnem zapolnjat' vtoroj takoj zhe massiv. Kogda vtoroj massiv okazhetsja zapolnennym, soljem dva massiva v odin, t.e. vyberem iz 20 elementov 10 s maksimal'nymi chastotami. Ochistim vtoroj massiv i stanem zapolnjat' ego snova, poka nam opjat' ne popadetsja 11-i element. Opjat' soljem 2 massiva (ili viberem 10 maksimalnih) i t.d. V konce u nas budet iskomyj element odnim iz 10 v pervom massive. Teper' delaem eshe odin prohod, podschityvaja chastoty tol'ko etih 10 elementov - i togda u nas budet okonchatel'nyj otvet.
Vozmozhno 10 elementov - dazhe bol'she chem nuzhno. Vpolne verojatno 2-3 dostatochno.
Algoritm rabotaet, dazhe esli elementy - ne chisla i predstavit' ih v vide korotkoj stroki ne predstavljaetsja vozmozhnym.
Ne znaju poka kak obosnovat', no dumaju chto esli element zanimaet bol'she poloviny spiska, to ego nevozmozhno raspredeli't po spisku takim obrazom, chtobi on ne popal v okonchatel'nyj massiv.
(Ответить) (Thread)
[User Picture]From: etonei
2004-07-12 04:23 am
Есть у меня вот какое бездоказательное подозрение.

Для удобства рассмотрим этот список как кольцо (мысленно замкнем начало с концом). Если значение X встречается больше чем в 50% элементов, то в кольце обязательно будут последовательности подряд идущих X-ов, причем длина максимальной такой цепочки будет больше всех других последовательностей подряд идущих одинаковых элементов.

За один проход находим максимальную цепочку одинаковых значений X, за второй - убеждаемся, действительно ли X-ов больше 60% в списке.
(Ответить) (Thread)
[User Picture]From: etonei
2004-07-12 04:37 am
Ooops, не работает :(
(Ответить) (Parent) (Thread)
[User Picture]From: scolar
2004-07-12 05:17 am

Любимая моя задачка про инварианты: если выкинуть два любых различных элемента, то решение новой задачи совпадает с решением исходной.
(Ответить) (Thread)
[User Picture]From: lom
2004-07-12 10:55 am
ык... упрощeнный коррeляционный фильтр.

Гeнeрируются случайная послeдоватeльность ( можно - по кругу, eсли выборка конeчная - с остатком от дeлeния по модулю N ) с попарным
сравнeниeм номeров, совпали + 1, нe совпали: -1, вeдeм сумму и сравниваeм с заранee выбранной константой...
(Ответить) (Thread)
From: ex_ilyavinar899
2004-07-12 02:26 pm
У меня есть подозрение, что если одно значение составляет больше половины элементов списка, то у него будут самая длинная последовательность, состоящая из одного значения.
(Ответить) (Thread)
[User Picture]From: avva
2004-07-12 02:32 pm
У меня есть подозрение, что если одно значение составляет больше половины элементов списка, то у него будут самая длинная последовательность, состоящая из одного значения.

Нет:

1 1 1 2 2 3 2 2 3 2 2 3 2 2 3
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2004-07-12 02:31 pm
Скоро напишу отдельную запись.
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>