Найти элементы, превышающие половину элементов массива | Набор 2

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти элементы, которые больше, чем половина элементов массива.

Примеры:

Input: arr[] = {1, 6, 3, 4}
Output: 4 6
Explanation:
Size of the array is 4. The elements which are greater than atleast N/2(= 4/2 = 2) elements of the array are 4 and 6.

Input: arr[] = {10, 4, 2, 8, 9}
Output: 10 9 8

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

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Подход на основе сортировки. См. предыдущий пост этой статьи о подходе на основе сортировки.

Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)

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

• Инициализируйте переменную, скажем, mid как (N + 1)/2 , чтобы сохранить средний индекс массива.
• Инициализируйте переменную, скажем, max , чтобы сохранить максимальный элемент массива.
• Инициализируйте массив count[] для хранения частоты каждого элемента.
• Обходим массив, arr[] и увеличиваем count[arr[i]] на 1.
• Пройдите по массиву count[] , используя переменную i сзади, и выполните следующие шаги:
  • Повторяйте до тех пор, пока значение count[i] не станет положительным, и выполните следующие шаги:
    • Выведите значение i и уменьшите значение count[i] и mid на 1 .
    • Если значение mid равно 0 , то выйти из цикла.
  • Если значение mid равно 0 , то выйти из цикла.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M), где M — максимальный элемент массива , arr[]
Вспомогательное пространство: O(M)