Task 101. Мажоритарный элемент массива

Задача: дан числовой массив размера N. Необходимо найти элемент, если такой существует, ктр встречается в массиве более чем [N / 2] раз (округление в меньшую сторону).

Входные данные: arr - числовой массив размера N, где N от 1 до 10000. Элементы массива - любые действительные числа.

Вывод: вывести мажоритарный элемент массива, если такой существует, иначе сообщение о его отсутствии.

Пример:

arr = [1, 2, 3, 4, 1, 1, 1]

Answer = 1

Идея: есть несколько способов решить эту задачу, рассмотрим самые оптимальные:

1. Используем хэш-таблицы. Запишем числа массива в HashMap<int, int> (в C# используем обьект Dictionary<int,int>): элемент массива -> кол-во вхождений в массив.Дальше найдем такой элемент HashMap, если такой существует, у ктр кол-во вхождений больше чем [размер массива / 2] (округляем в меньшую сторону).
2. Алгоритм Бойера-Мура. Он также решает задачу за O(N) по времени, но при этом использует меньше памяти, чем вариант с хэш-таблицей. Мы более детально рассмотрим этот алгоритм в следующих задачах, а пока вы можете ознакомиться с этим подходом в статье на хабре:
   Поиск часто встречающихся элементов в массиве

Реализация:

https://gist.github.com/unilecs/db72766a8768791edb7e64ae44434932

Test:

https://dotnetfiddle.net/OhWpWb