Напишите алгоритм, чтобы найти наиболее часто встречающийся элемент в массиве. Дай время сложность алгоритма

Я проснулся с заданием «Анализ алгоритма» и застрял в этом вопросе, я должен представить его завтра, и мне нужна помощь. Пожалуйста, ответьте, если вы можете решить это.

Учитывая массив A из n чисел, напишите эффективный алгоритм, чтобы найти наиболее часто
произошел элемент в этом массиве (режим этого массива). Также проанализируйте временную сложность вашего
алгоритм.

-4

Решение

Поскольку это задание, я дам вам подсказку только о верхних границах сложности и аналогичной проблеме.

Эта проблема немного сложнее, чем Проблема отличимости элемента1. Проблема отличимости элементов известна как не может быть решена лучше, чем O(nlogn) худший случай. Решения для отличимости элементов:

  1. Сортировать и повторять — O(nlogn)
  2. Создайте набор / гистограмму элементов и проверьте уникальность. Это сделано с помощью Hashtables в O(n) средний случай и O(n^2) худший случай и O(n) дополнительное пространство

Подумайте об обоих подходах и подумайте, как вы можете изменить их, чтобы решить вашу проблему.

Кроме того, нижняя граница отличимости элементов говорит о том, что не будет лучшего алгоритма, чем O(nlogn) худший случай.


(1) Проблема Различия Элементов: Все ли элементы в массиве различны? Или есть какой-то элемент, который также имеет дубликат самого себя?

1

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector