我有一个问题，其一些修改后减少到“在测距数大于x的至少指数[L，R]”查找数大于x的范围

例如：假设一阵列A = {1, 2, 3, 6, 9, 8, 4, 3, 7, 6, 2}

而查询是“找到至少一个元素的索引在数组A中的范围为[2,6]，这是大于或等于5”

回答为上述查询是4（用于值此指数为6）（指数以1为基础）

有多个查询，数组没有排序（考虑到输入已经在内存中）

有没有一种算法，在O（logN）中查询是可能的，其中N是否定的。排列A中的元素。

2016-03-07 Akashdeep Saluja

如果范围[a，b]在排序顺序中包含自然数a <= n <= b，那么您可以使用二分搜索在O（log N）中解析N = #elements。 – blazs

你可以在O（（logN）^ 2）中完成。构建可以在范围内获得最大值的元素的分段树。然后在[A，B]范围内进行二分搜索，在该范围内您尝试查找最小索引> = A，其中范围[A，索引]中的最大元素> = q。使用分段树来获取范围[A，索引]中的最大值。这有意义吗？ – Ghooo

@Ghooo它看起来像这个问题的正确解决方案。我怀疑我们可以在线执行'O（logN）'中的每个查询。 –

在构建一个占用O（N）空间的数据结构后，实际上有很多方法可以在O（log N）时间内支持查询。

易于理解的答案

做一个二叉树A的元素为叶，通过索引排序。
在每个内部节点中，记录叶子在其子树中的最大值
您需要能够找到给定其索引的节点的路径。如有必要，记录每个内部节点中第一个叶子的索引。没有这个，你可以通过建立一个方便的形状来建造你的树。
现在，用一个价值发现的最小指数> = L> = X：
- 查找树A [L]路径
- 如果A [L] < X，然后去了直到找到包含值> = X的右侧叔叔为止的树，沿着叔叔树找到值> = X的第一个叶子。下降时，如果左边的孩子有一个> = X（检查存储的最大值），然后向左。否则，向右走。

超高效答案

为了使上述算法真正有效，可以在树编码到一个数组，像我们的堆做。在这种表示中（使用基于1的索引），您有一个数组，其中包含N-1个内部节点的最大值，然后是N个叶子。调用该数组H。然后H[i]的孩子在H[i*2]和H[i*2+1]。的H[i]父是H[i>>1]

伪代码，使用基于1的索引，我们给出：

A[] = input array, N = input array size

我们建立^ h这样的：

H = new array with size N*2-1, indexed from 1 to N*2-1 
for (int i=1; i<=N; ++i) 
    H[i+N-1]=A[i]; 
for (int i=N-1; i>0; --i) 
    H[i] = max(H[2*i],H[2*i+1]);

需要注意的是我们创造的孩子在父母面前，让孩子们在那里，当我们需要得到最大的价值。现在

，查询功能：

//get the index of the first element with val >= minval, index >= minindex, and index <= maxindex 
//returns -1 if there is no such element 

firstAtLeast(minval, minindex, maxindex) 

    if (maxindex < minindex) 
     return -1; 

    node = minindex+N-1; //find minindex in the tree 

    //go up and right until we find a subtree that has a value >= minval 

    while(H[node] < minval) 

     //if we are a right child of our parent, go up until 
     //we have a right sibling 
     while((node&1) == 1) //node is odd 
      node = node>>1; //same as floor(node/2); 
      if (node <= 1) 
       //we went up to the root 
       //there is no such element 
       return -1; 

     //now node is a left child. try its right sibling   
     ++node; 

    //We found a subtree. get the first valid leaf 

    while(node < N) //while it's an internal node 
     node = 2*N; //left child 
     if (H[node] < minval) 
      ++node; //left child not valid - move to right child 

    //Found leaf. get index in A[i] and check against maxindex 

    index = node-(N-1); 
    return (index <= maxindex ? index : -1);

这满足了为O查询（日志N）的时间的要求。如果知道不会有小于maxindex的回答，那么退出的时间会很长（也不会太困难），但这会使伪代码不那么清晰，所以我将其留作练习

来源

2016-03-07 16:17:59

制作二叉树后，需要O（N log N）的时间，而不是在OP的原始注释中提到的O（N）。 –

它只需要O（N）来制作二叉树。您不必通过重复插入来构建它 –

@ShaneMacLaughlin解释如何在O（N）中构建树时，如果您已经知道排序，则不适用于评论。如果你想打开一个问题，我会回答 –

O（logN）接缝是不可能的。您至少需要读取输入，直到第一个元素更大（这可能是最后一个元素或根本没有）。所以在最坏的情况下，你需要读取整个输入，这意味着O（N）。如果你输入像的一些额外的结构来分类比你能改进算法O（logN）的

改善时才有可能。

如果有多重查询，您仍然需要O（logN）。您可以一次检查多个查询，并且还可以缓存相同查询再次出现的结果。

来源

2016-03-07 11:08:45 MrSmith42

编辑该问题。输入在内存中。并且针对不同的范围和不同的搜索值有多个查询。 –

如果可能元素的数量很小（比如说K）并且可以很容易地枚举，那么对于N个元素的数组，您可以使用counting sort按顺序N + K排序它们。然后，您可以使用二进制搜索来查询您的查询，这将成为订单日志N.注意，计数排序还需要订购K存储器，因此仅适用于相对少量的离散按键在使用时。如果您有Q查询，则复杂度为O（（N + K）+ Q（log（N））

来源

2016-03-07 11:35:34

你能解释如何在排序后执行每个查询吗？ –

给定范围L的低端和范围H的高端，搜索L，如果最近添加一个索引位置 H，搜索H减1，称为结果IH。如果IL <= IH返回IL否则返回未找到。注意这是2 log N也是O（log N）。 –

我没有得到你以前的评论，使用计数排序排序后，你如何使用二进制搜索。 –

如果您有很多查询，并且数据量适中，则可能会获得体面通过O（N）额外存储加速您的查询

创建一个元组aarray (a[i], i)（即数组中的值，该值的索引），按第一个排序（并且在冲突的情况下，然后使用二进制搜索来找到您的起点，如果该指数超出您的范围，请继续遍历您的排序列表，直到您找到一个落在您感兴趣的范围内的指数。

我怀疑这个算法是O（N），最坏的情况是，所以我想它有可能做得更好。

来源

2016-03-07 12:53:40 Vatine

查找数大于x的范围

回答

易于理解的答案

超高效答案

相关问题