2019-gate-computer-science-and-it-practice.pdf/Q04-alg2

Вопрос: Q04-alg2-31d68c

Пусть дана последовательность n случайных чисел.

Какая будет временная сложность (в наихудшем случае) для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

Ответы

• Правильный ответ:

Объяснение

Официальный ответ у них: Решение состоит в том, чтобы завести два цикла и отслеживать максимальное количество для всех различных элементов. Если максимальное количество становится больше n/2, то циклы завершаются и возвращается элемент с максимальным количеством. Если в конце максимальное количество не превышает n/2, то такой элемент не существует.

Мысли Стаса: Фиг знает, вроде же легко

• пиромидально или слиянием отсортировать (),
• потом пробежаться по отсортированному списку, посчитывая в одном счетчике последовательное число элементов ()
• уложимся в
• WTF?

Исходники — вопрос 4 на 226 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.