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