如果允许预处理且不计入时间复杂度，那么可以使用它来构建子列表，以便您可以高效地找到要查找的元素。与大多数优化一样，这会用空间换时间。
预处理步骤是将原始的n个数字列表创建为许多新的子列表。
每个子列表都是原始列表的一部分，从第n个元素开始，延伸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]
惰性求值的代码略微复杂（但只是略微），因此我不会为其提供伪代码。
然后，要查找范围i到j（其中i和j是原始索引）中第k个最小数，只需查找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 "====="
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
=====
[1,n]内查找第k个元素就很容易了。但是如果要查找区间[i,j]内的第k个元素呢？再次对区间[i,j]内的元素排序吗？NO！ - Alcottk可以从查询到查询改变，我们需要整个子列表的信息。 - Roasted Yam