Найти конкретные числа частоты в несортированном массиве

Question

У меня вопрос:

У меня есть несортированный массив с n числами,
Мне нужно найти числа, которые появляются более чем на 10% в массиве.
Можете ли вы написать мнепсевдокод со сложностью Времени

Пример:

array A = {12,11,1,3,1,4,4,7,8,9,10}

Ответ 1,3.

Answer 1

Вы можете использовать Хеш-таблицу (Hash Map), чтобы решить эту проблему.

Итерируйте свой массив, если хеш-таблица не содержит ваш элемент (число), затем добавьте его со счетчиком, установленным на 1, иначе приращениесчетчик на 1. Итерируйте вашу хеш-таблицу и сохраняйте каждую запись, где счетчик составляет более 10% размера массива.

Сложность по времени - это стоимость итерации массива (n) плюс итерации хешатаблица (наихудший случай: n): O (n) = 2n

Другим решением будет сортировка массива, а затем итерация его с подсчетом каждого элемента и сохранением элемента, если счет больше 10%

Сложность по времени - это стоимость вида (n log (n)) плюс стоимость итерации массива (n): O (n) = n + n log (n)