Алгоритм времени O (klogn) для нахождения k-го наименьшего элемента из дерева Фенвика
Я имею в виду, чтобы найти kth наименьшая фактическая частота в Fenwick-Tree в O(k log(n)) время.
Если мои данные:
Tree = [1,3,1,10,3]
Actual frequency = [1,2,1,6,3]
Таким образом, второй наименьший элемент будет по индексу 1.
Решение
Вам нужна k-я наименьшая фактическая частота, которую, я думаю, невозможно определить без сортировки фактических частот. Если единственное, что у вас есть, это дерево Фенвика, то вы можете вычислить последовательность фактических частот в О (п * журнала (п)) время (поскольку вы можете рассчитать каждую фактическую частоту в O (log (n)) (см. Вот), и у вас есть n частот). Сортировка последовательности фактических частот по быстрой сортировке занимает О (п * журнала (п)), и нахождение k-го элемента отсортированной последовательности занимает На) (могут быть записи с одинаковой фактической частотой, поэтому вы не можете сделать это в O (1); но вы можете использовать линейный поиск). Таким образом, весь поиск может быть выполнен в O (n * log (n)).
Надеюсь это поможет. Я понятия не имею, как это можно сделать в O (k * log (n)).
Другие решения
Ну, я подумал о возможном решении,
while(start<=end){
int mid=(start+end)>>1;
if(read(mid)>=k)end=mid-1; // read(mid) returns the cummulative frequency.
else start=mid+1;
}
начало должно быть ответом.