0

Недавно надо было сделать задачу, в которой одной из подзадач являлось нахождение наиболее часто встречающегося элемента в массиве. Если вдруг кто не понял, пример:

Дан массив: 3 4 5 3 6 7 5 3 4 3 3 8 5 4

Тут чаще всего встречается тройка. Вот ее и надо вывести

Натолкните на идею\алгоритм, с пом.которого можно это все реализовать?

p.s. вариантом решения было такое: создать массив, размерность которого - максимально возможный элемент в массиве, затем в этот массив прибавлять по единичке, когда встречаешь из первого массива элемент. Так пройтись по массиву, и затем отсортировать второй массив по возростанию и вывести последний элемент. Но думаю, что это малость извращение.

5
  • Это на каких олимпиадах такие задачки дают?
    – DreamChild
    16 мая 2014 в 19:11
  • Яндекс. Алгоритмы
    – hamsternik
    16 мая 2014 в 19:16
  • это какая? сёдня не было такой
    – qulinxao
    16 мая 2014 в 19:47
  • хочешь извращаться? Да здравствуют ассоциативные массивы! )
    – b2soft
    16 мая 2014 в 19:59
  • Должно сработать: arr.GroupBy(x => x).OrderByDescending(g => g.Count).First().Key
    – VladD
    16 мая 2014 в 20:08

2 ответа 2

4

если ничего не известно , то только сортировка и затем подсчёт повторов и выбор самого частого.

если же заведомо известно , что самый частный элемент больше чем в половине элементов то есть простой алгоритм ( догадайся , либо выгугли)

если же заведомо известно в каком диапазоне элементы , то можно счётчиком.

в иных случаях - иные специфические особенности.

3
  • 1
    Сортировка-то зачем? Сортировать будете в лучшем случае за NlogN, а потом еще потребуется линейное время на проход по массиву. А можно просто пройтись по массиву с подсчетом элементов в хэштаблице без какой-либо сортировки и проход по счетчикам.
    – a_gura
    16 мая 2014 в 22:57
  • 3
    a_gura допускает очень типичную ошибку, забывая о времени на поиск в хэштаблице. Если для каждого элемента массива выполнить такой поиск, а в ряде случаев еще и модификацию хэштаблицы, то количество операций будет намного больше NlogN. В данном случае по скорости ничего быстрее сортировки не сделать. Лично на практике неоднократно убеждался в этом. Задача в общем-то типовая. На больших массивах разницу в скорости получал на порядок и выше. Решение с хэштаблицой в ряде случаев может быть проще/удобнее по реализации, но сортировка быстрей.
    – reshu
    16 мая 2014 в 23:18
  • 1
    Ура, в кои-то веки алгоритмическая дискуссия! Вброшу-ка и я: но ведь вставка в hash table O(1), разве нет?
    – VladD
    17 мая 2014 в 8:56
1

Наиболее простой для понимания алгоритм: создание второго массива b [0, 1, 2...] для каждого из чисел и инкремент, например, b[5] при нахождении в a[47] числа 5.

Лично я могу посоветовать тебе прочитать про алгоритм Бойера-Мура. Это очень простой, маленький и быстрый алгоритм.

4
  • А если числа в исходном массиве 64-битные, какого размера собираетесь заводить массив b?
    – VladD
    17 мая 2014 в 9:31
  • Это как очень простой для понимания алгоритм. Я же не говорю, что нужно использовать его всегда и везде! На мой взгляд, он подходит только для обучения. 17 мая 2014 в 9:34
  • @Platon-Efimov: вообще-то, это вариант предыдущего ответа: сортировка подсчётом.
    – VladD
    17 мая 2014 в 9:46
  • Ага, окей, я понял, вообщем даже после создания массива нужен будет строковый алгоритм. Сразу вопрос в тему строк: что лучше: КМП или БМ??
    – hamsternik
    17 мая 2014 в 11:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.