10

这是问题，一个未排序的数组a[n]，我需要找到kthrange 中的最小数字[i, j]，并且 absolute 1<=i<=j<=n, k<=j-i+1。

通常我会用quick-find它来完成这项工作，但是如果有许多不同范围的查询请求，它就不够快[i, j]，我很难找出一个算法来及时进行查询O(logn)（允许预处理）。

任何想法都值得赞赏。

附言

让我让问题更容易理解。允许进行任何类型的预处理，但查询需要在 O(logn) 时间内完成。并且会有很多（超过 1 个）查询，比如 find 1st in range [3,7], or 3rd in range [10,17], or 11th in range [33, 52].

范围 [i, j]我的意思是在原始数组中，没有排序或其他东西。

例如a[5] = {3,1,7,5,9}，查询1st in range [3,4]是5，2nd in range [1,3]是5，3rd in range [0,2]是7。

4

6 回答 6

7

如果允许预处理并且不计入时间复杂度，只需使用它来构建子列表，以便您可以有效地找到您正在寻找的元素。与大多数优化一样，这以空间换时间。

您的预处理步骤是获取原始n数字列表并创建许多新的子列表。

这些子列表中的每一个都是原始的一部分，从n第 th 个元素开始，扩展m元素，然后排序。所以你的原始清单：

 {3, 1, 7, 5, 9}

给你：

 list[0][0] = {3}
 list[0][1] = {1, 3}
 list[0][2] = {1, 3, 7}
 list[0][3] = {1, 3, 5, 7}
 list[0][4] = {1, 3, 5, 7, 9}

 list[1][0] = {1}
 list[1][1] = {1, 7}
 list[1][2] = {1, 5, 7}
 list[1][3] = {1, 5, 7, 9}

 list[2][0] = {7}
 list[2][1] = {5, 7}
 list[2][2] = {5, 7, 9}

 list[3][0] = {5}
 list[3][1] = {5,9}

 list[4][0] = {9}

这不是一个便宜的操作（在时间或空间上），因此您可能希望在列表上维护一个“脏”标志，以便您仅在执行修改操作（插入、删除、更改）后第一次执行它。

事实上，您可以使用惰性求值来提高效率。基本上在您开始和执行修改操作时将所有子列表设置为空列表。然后，每当您尝试访问子列表并且它为空时，请在尝试从中获取第kth 值之前计算该子列表（并且仅那个）。

这样可以确保仅在需要时评估子列表并缓存以防止不必要的重新计算。例如，如果您从不要求从 3 到 6 子列表中的值，则永远不会计算它。

创建所有子列表的伪代码基本上是（for两端都包含循环）：

for n = 0 to a.lastindex:
    create array list[n]
    for m = 0 to a.lastindex - n
        create array list[n][m]
        for i = 0 to m:
            list[n][m][i] = a[n+i]
        sort list[n][m]

惰性求值的代码稍微复杂一点（但只是一点点），所以我不会为此提供伪代码。

然后，为了找到范围内的k第 th 最小数（其中和是原始索引），您只需查找，这是一个非常快速的 O(1) 操作：ijijlists[i][j-i][k-1]

                +--------------------------+
                |                          |
                |                          v
1st in range [3,4] (values 5,9),   list[3][4-3=1][1-1-0] = 5
2nd in range [1,3] (values 1,7,5), list[1][3-1=2][2-1=1] = 5
3rd in range [0,2] (values 3,1,7), list[0][2-0=2][3-1=2] = 7
|             |                         ^    ^    ^
|             |                         |    |    |
|             +-------------------------+----+    |
|                                                 |
+-------------------------------------------------+

这是一些 Python 代码，它显示了这一点：

orig = [3,1,7,5,9]
print orig

print "====="
list = []
for n in range (len(orig)):
    list.append([])
    for m in range (len(orig) - n):
        list[-1].append([])
        for i in range (m+1):
            list[-1][-1].append(orig[n+i])
        list[-1][-1] = sorted(list[-1][-1])
        print "(%d,%d)=%s"%(n,m,list[-1][-1])

print "====="
# Gives xth smallest in index range y through z inclusive.
x = 1; y = 3; z = 4; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
x = 2; y = 1; z = 3; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
x = 3; y = 0; z = 2; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
print "====="

正如预期的那样，输出是：

[3, 1, 7, 5, 9]
=====
(0,0)=[3]
(0,1)=[1, 3]
(0,2)=[1, 3, 7]
(0,3)=[1, 3, 5, 7]
(0,4)=[1, 3, 5, 7, 9]
(1,0)=[1]
(1,1)=[1, 7]
(1,2)=[1, 5, 7]
(1,3)=[1, 5, 7, 9]
(2,0)=[7]
(2,1)=[5, 7]
(2,2)=[5, 7, 9]
(3,0)=[5]
(3,1)=[5, 9]
(4,0)=[9]
=====
(1,3,4)=5
(2,1,3)=5
(3,0,2)=7
=====
于 2013-03-06T01:31:54.400 回答
6

当前的解决方案是 O( (logn)^2 )。我很确定它可以修改为在 O(logn) 上运行。该算法相对于 paxdiablo 算法的主要优势在于空间效率。该算法需要 O(nlogn) 空间，而不是 O(n^2) 空间。

首先，从长度为 m 和 n 的两个排序数组中找到第 k 个最小元素的复杂度是 O(logm + logn)。从长度为 a,b,c,d.. 的数组中找到第 k 个最小元素的复杂度是 O(loga+logb+.....)。

现在，对整个数组进行排序并存储它。对数组的前半部分和后半部分进行排序并存储，依此类推。您将有 1 个长度为 n 的排序数组、2 个长度为 n/2 的排序数组、4 个长度为 n/4 的排序数组，依此类推。所需的总内存 = 1*n+2*n/2+4*n/4+8*n/8...= nlogn。

一旦你有 i 和 j 找出子数组的列表，当它们连接时，给你范围 [i,j]。将有 logn 个数组。找到其中第 k 个最小的数字将花费 O( (logn)^2) 时间。

最后一段的示例：假设数组大小为 8（索引从 0 到 7）。您有以下排序列表：

A：0-7，B：0-3，C：4-7，D：0-1，E：2-3，F：4-5，G：6-7。

现在用指向这些数组的指针构造一棵树，这样每个节点都包含它的直接组成部分。A 将是根，B 和 C 是它的孩子，依此类推。

现在实现一个返回数组列表的递归函数。

def getArrays(node, i, j):
    if i==node.min and j==node.max:
        return [node];

    if i<=node.left.max:
        if j<=node.left.max:
            return [getArrays(node.left, i, j)];  # (i,j) is located within left node
        else:
            return [ getArrays(node.left, i, node.left.max), getArrays(node.right, node.right.min, j) ]; # (i,j) is spread over left and right node 
    else:
        return [getArrays(node.right, i, j)]; # (i,j) is located within right node
于 2013-03-06T03:55:39.727 回答
3

预处理：创建一个 nxn 数组，其中 [k][r] 元素是前 r 个元素中的第 k 个最小元素（为方便起见，索引为 1）。

然后，给定一些特定的范围 [i,j] 和 k 的值，执行以下操作：

  1. 在矩阵的 [k][j] 槽处找到元素；称之为 x。
  2. 沿着矩阵的 i-1 列，找出其中有多少值小于或等于 x（将第 0 列视为具有 0 个较小的条目）。通过构造，该列将被排序（所有列都将被排序），因此可以在日志时间内找到它。将此值称为 s
  3. 在矩阵的 [k+s][j] 槽中找到元素。这是你的答案。

例如，给定 3 1 7 5 9

  • 3 1 1 1 1
  • X 3 3 3 3
  • XX 7 5 5
  • XXX 7 7
  • XXXX 9

现在，如果我们被问到 [2,4] 范围内的第二小（同样，1 索引），我首先找到 [1,4] 范围内的第二小，即 3。然后我查看第 1 列和看到有 1 个元素小于或等于 3。最后，根据需要，我在 [3][5] 插槽的 [1,4] 范围内找到了第 3 个最小的元素，即 5。

这需要 n^2 空间和 log(n) 查找时间。

于 2013-03-06T03:25:21.007 回答
1

这个不需要预处理，但比O(logN). 它比简单的迭代和计数要快得多，并且可以支持对序列的动态修改。

它是这样的。假设长度n有n=2^x一些x。构造一个根节点表示的段树[0,n-1]。对于每个节点，如果它代表一个节点[a,b], b>a，让它有两个子节点，每个子节点代表[a,(a+b)/2], [(a+b)/2+1,b]。（也就是说，进行递归除以二）。

然后，在每个节点上，为该段中的数字维护一个单独的二叉搜索树。因此，对序列的每次修改都需要O(logN)[on the segement]*O(logN)[on the BST].查询可以这样完成，让x 在段内Q(a,b,x)的排名[a,b]。显然，如果Q(a,b,x)可以有效地计算，则二进制搜索x可以有效地计算所需的答案（使用额外的O(logE)因子。

Q(a,b,x)可以计算为：找到组成的最小段数[a,b]，这可以在O(logN)段树上完成。对于每个段，在该段的二叉搜索树上查询小于 的元素数x。将所有这些数字相加得到Q(a,b,x).

这应该是O(logN*logE*logN)。嗯，不完全是你所要求的。

于 2013-03-06T08:58:44.453 回答
0

在 O(log n) 时间内，不可能读取数组的所有元素。由于没有排序，也没有提供其他信息，这是不可能的。

于 2013-03-06T01:27:29.983 回答
-1

在最坏情况和平均情况下，没有办法比 O(n) 做得更好。您必须查看每一个元素。

于 2013-03-06T01:28:41.827 回答