20: Majority item

Дан массив чисел. Найдите элемент который встречается больше чем ⌊n/2⌋ раз

Замечание: Наиболее часто встречающийся элемент всегда существует

 

Пример 1

Input: [1, 1, 3]

Output: 1

Пример 2

Input: [1, 1, 3, 3 ,4, 3]

Output: 3