Нахождение k t h k ^ {th} k-й наименьший элемент массив (эффективно) сначала может показаться немного сложным; однако его можно легко найти с помощью минимальной кучи или путем сортировки массива.
Алгоритм
Для поиска используются следующие шаги. k t h k^{th} k-й наименьший элемент с использованием сортировки.
-
Отсортируйте данный массив в порядке возрастания, используя алгоритм сортировки, такой как сортировка слиянием, пузырьковая сортировка или сортировка кучи.
-
Вернуть элемент с индексом k — 1 k — 1 k − 1 в отсортированном массиве.
Иллюстрация ниже дополнительно поясняет эту концепцию:
Рассмотрим массив, показанный выше.
1 из 4
Реализация
Следующий фрагмент кода реализует вышеуказанный алгоритм на C ++:
#include # включить с использованием пространства имен std; int main () {int arr [] = {10, 1, 0, 8, 7, 2}; int size = sizeof (arr)/sizeof (arr [0]); //Сортировка массива sort (arr, arr + size); //Нахождение третьего наименьшего элемента в массиве cout
