K-й по величине элемент в дереве N-массива

Для данного N-массивного дерева, состоящего из N узлов и целого числа K , задача состоит в том, чтобы найти K ^-й наибольший элемент в заданном N-арном дереве .

Примеры:

Input: K = 3

Output: 77 
Explanation:
The 3rd largest element in the given N-array tree is 77.

Input: K = 4

Output: 3

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

• Инициализируйте переменную, скажем, самый большойELE как INT_MIN.
• Определите функцию, например, самый большойEleUnderRange(root, data) и выполните следующие шаги:
  • Если значение текущего корня меньше, чем данные, то обновите значение наибольшего ELe как максимум наибольшего ELe и значение текущего корня.
  • Выполните итерацию по всем дочерним элементам текущего корня и рекурсивно вызовите функциюlargeEleUnderRange(child, data) .
• Инициализируйте переменную, скажем, как INT_MAX , чтобы сохранить K ^-й самый большой элемент.
• Итерация по диапазону [0, K – 1] рекурсивно вызывает функцию НаибольшийEleUnderRange(root, ans) и обновляет значение ans как самый большойELe и самый большойELe как INT_MIN .
• После выполнения вышеуказанных шагов выведите значение ans в качестве результирующего K ^-го максимального значения.

Ниже приведена реализация описанного выше подхода.

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