![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaХорошая программистская задачка:
Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).
Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.
P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).
Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.
P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-07-11 06:30 pm (UTC)no subject
Date: 2004-07-11 06:36 pm (UTC)Но в принципе в условии задачи не сказано, можно ли модифицировать список. Ясно, что лучше обойтись без модификации, но я не скажу, можно без неё обойтись или нельзя ;)
no subject
Date: 2004-07-11 06:44 pm (UTC)no subject
Date: 2004-07-11 06:47 pm (UTC)no subject
Date: 2004-07-11 06:49 pm (UTC)no subject
Date: 2004-07-11 06:49 pm (UTC)красивого и быстрого решения придумать не могу... в математике не силён... (:
no subject
Date: 2004-07-11 06:50 pm (UTC)no subject
Date: 2004-07-11 06:57 pm (UTC)no subject
Date: 2004-07-11 06:58 pm (UTC)Можно предположить, что размер списка и все релевантные величины умещаются, скажем, в 32 бита. Т.е. переменная, подсчитывающая размер массива, считается занимающей фиксированное количество памяти. То же самое касается переменной, хранящей копию элемента списка.
(при этом, естественно, воспользоваться этим как лазейкой и объявить "фиксированный" дополнительный массив размером в 2^32, или, ещё удобнее, в 2^N, где N - количество битов для записи каждого элемента, не разрешается. Если надо быть совсем точным, можно разрешить память, кол-во которой равно линейной функции от суммы кол-ва битов для представления элемента и кол-ва битов для представления размера массива. Но на практике никто так не делает и просто говорят о константной памяти).
no subject
Date: 2004-07-11 07:21 pm (UTC)no subject
Date: 2004-07-11 07:27 pm (UTC)no subject
Date: 2004-07-11 07:30 pm (UTC)no subject
Date: 2004-07-11 07:33 pm (UTC)Но требует дополнительной памяти, линейной от размера исходного списка (для хранения промежуточных данных во время рекурсивных вызовов алгоритма для нахождения медианы).
no subject
Date: 2004-07-11 07:52 pm (UTC)no subject
Date: 2004-07-11 08:02 pm (UTC)Если разделить список на пары, то если член "х" –– большинство, то, если искомый член "х" есть, то, если пары, где члены разные, повыкидывать, то
число пар, где оба члена –– "х" должно быть больше, чем число пар, где оба члена –– "не х". Как предельный случай можно поиграть со списком их а+1 белых и а–1 черных.
Значит действуем так: игнорируем все смешанные пары и ставим счетчик на 0. Идем до первой одинаковой пары, замечаем ее члены как кандидата на большинство, ставим счетчик на 1. Если следующая одинаковая пара такая же, то увеличиваем счетчик на 1, если она другая, вычитаем из счетчика 1. Если счетчик оказывается на 0, то следующая одинаковая пара дает нам кандидата и 1 в счетчике.
В процессе узнаем сколько членов в списке.
Если в конце процесса имеем не 0 в счетчике и кандидата, то на следующем прогоне считаем сколько найдем кандидата в списке. Если >50%, ура.
На нечетное число членов тривиально распространимо, но писать лень.
no subject
Date: 2004-07-11 08:20 pm (UTC)no subject
Date: 2004-07-11 08:23 pm (UTC)Если счетчик > 0, то два.
Первый для определения кандидата и числа членов в списке.
Второй для проверки, в большинстве ли кандидат.
no subject
Date: 2004-07-11 08:25 pm (UTC)no subject
Date: 2004-07-11 08:30 pm (UTC)no subject
Date: 2004-07-11 08:35 pm (UTC)no subject
Date: 2004-07-11 08:42 pm (UTC)no subject
Date: 2004-07-11 08:43 pm (UTC)no subject
Date: 2004-07-11 08:44 pm (UTC)no subject
Date: 2004-07-11 08:49 pm (UTC)no subject
Date: 2004-07-11 08:50 pm (UTC)Нет никого больше половины.