K-й наименьший элемент в N-арном дереве
Учитывая N-массивное дерево (Общее дерево) и целое число K , задача состоит в том, чтобы найти K -е наименьшее элемент в дереве N-массива.
Примеры:
Input: 10
/ /
2 34 56 100
/ | / |
77 88 1 7 8 9
K = 3
Output: 7
Explanation: 7 is the 3rd smallest element in the tree. The first two smallest elements are 1 and 2 respectively.Input: 1
/
2 3 4
/
5 6
K = 4
Output: 4
Подход: проблему можно решить, найдя наименьший элемент в заданном диапазоне K раз и продолжая обновлять верхний конец диапазона до наименьшего найденного элемента. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте глобальную переменную, скажем, MinimumElement как INT_MAX .
- Объявите функцию smallEleUnderRange(root, data) и выполните следующие операции:
- Если root.data больше, чем data , тогда обновите MinimumElement как min для MinimumElement и root.data.
- Перебрать все дочерние элементы корня . Вызовите рекурсивную функцию наименьшийEleUnderRange(дочерний элемент, данные).
- Объявите функцию KthSmallestElement(root, k) для выполнения следующих операций:
- Инициализируйте переменную, скажем, как INT_MIN , для хранения K -го наименьшего элемента .
- Переберите диапазон [0, K – 1] , используя переменную i , и выполните следующее:
- Вызовите функцию smallEleUnderRange (root, ans) , а затем обновите ans как MinimumElement , а затем MinimumElement как INT_MAX.
- Наконец, выведите ans в качестве требуемого ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * K), где N — количество узлов в данном дереве.
Вспомогательное пространство: O(1), но стек рекурсии использует максимум O(N) пространства.