这是问题,一个未排序的数组a[n],我需要找到kth范围内的最小数字[i, j],绝对是1<=i<=j<=n, k<=j-i+1.
通常我会quick-find用来完成这项工作,但是如果有很多不同范围的查询请求就不够快[i, j],我很难找出算法及时进行查询O(logn)(允许预处理).
任何想法都表示赞赏.
PS
让我更容易理解这个问题.允许任何类型的预处理,但查询需要在O(logn)时间内完成.并且会有很多(超过1个)查询,比如查找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.
如果允许预处理而不计入时间复杂度,只需使用它来构建子列表,以便您可以有效地找到您正在寻找的元素.与大多数优化一样,这会占用时间空间.
您的预处理步骤是获取原始的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}
这不是一个便宜的操作(在时间或空间上),因此您可能希望在列表上维护"脏"标志,这样您只能在执行修改操作(插入,删除,更改)后第一次执行它.
实际上,您可以使用延迟评估来提高效率.当您启动时以及执行修改操作时,基本上将所有子列表设置为空列表.然后,每当您尝试访问子列表并且它为空时,在尝试从中获取该k值之前,计算该子列表(仅限该列表).
这样可确保仅在需要时对子列表进行评估并缓存以防止不必要的重新计算.例如,如果您从未要求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范围届最小的数i通过j(其中i和j是原始索引),您只需仰望lists[i][j-i][k-1],非常快的O(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
=====
当前的解决方案是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].将有数组的登录号.在其中找到第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将是root,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