4

我的意思是及时找到kthFenwick-Tree 中的最小实际频率O(k log(n))。
如果我的数据是：

Tree = [1,3,1,10,3]
Actual frequency = [1,2,1,6,3]

所以第二小的元素将在索引 1 处。

4

2 回答 2

0

您需要第 k 个最小的实际频率，我认为如果不对实际频率进行排序就无法确定。如果您唯一拥有的是 Fenwick 树，那么您可以在O(n*log(n))时间内计算实际频率的序列（因为您可以在 O(log(n)) 中计算每个实际频率（参见这里），你有 n 个频率）。通过快速排序对实际频率序列进行排序需要O(n*log(n))，找到排序序列的第 k 个元素需要O(n)（可能存在具有相同实际频率的条目，因此您不能在O(1); 但你可以使用线性搜索）。所以整个搜索可以在 O(n*log(n)) 中完成。

希望这可以帮助。我不知道如何在 O(k*log(n)) 中做到这一点。

于 2013-07-13T00:42:59.770 回答
-2

好吧，我想到了一个可能的解决方案，

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;
}

开始必须是答案。

于 2013-07-12T23:30:10.260 回答