Тема: Найти суперэлемент во входном потоке

Помогите, пожалуйста, с задачкой:

На вход подается поток из N чисел (каждое можно считать только один раз). Известно, что среди них есть суперэлемент, который встречается не менее, чем N/2 раз. Найти этот элемент, использовав O(1) памяти.

2

Re: Найти суперэлемент во входном потоке

алгоритм Бойера-Мура (не тот, что относится к строкам, другой)

3

Re: Найти суперэлемент во входном потоке

a.a.maleev пишет:

Помогите, пожалуйста, с задачкой:

На вход подается поток из N чисел (каждое можно считать только один раз). Известно, что среди них есть суперэлемент, который встречается не менее, чем N/2 раз. Найти этот элемент, использовав O(1) памяти.

Может быть, не "не менее", а "больше"? Иначе задача может иметь не единственное решение.

И если действительно "больше", то решать можно так: просто для каждого бита посчитать, сколько раз в
том бите стоит 0 среди N чисел, а сколько - 1, и выбрать самое популярное значение. Т.е. надо будет K ячеек памяти (где K - число бит во входных числах), т.е. O(1), если это заранее известная константа.

4

Re: Найти суперэлемент во входном потоке

А у тебя получилось решить задачу?

We provide guarantee to cert killer 70-462 gmat with online exam 400-051 training itil and  you can also get best quality.