segment-tree - 如何在数组的区间内找到第k个最小的元素

Question

a[]假设我有一个长度为的未排序整数数组N。现在我想找到给定区间a[i]-a[j]( 1 <= i <= j <= N) 内的第 k 个最小整数。例如：我有一个数组a[10]={10,15,3,8,17,11,9,25,38,29}。a[2]-a[7]现在我想找到区间内的第三个最小元素。答案是 9。我知道这可以通过对该区间进行排序来完成。但这需要O(Mlog(M))( M = j - i + 1) 时间。另外，我知道，这可以通过段树来完成，但我不明白如何修改它来处理这样的查询。

Answer 1

您可以使用Quickselect （快速排序的一种修改）来查找列表中的第 k^个最小/最大值。为了简单起见，我们假设您尝试对整个数组执行此操作（请注意，没有区别）。

本质上您使用快速排序，但只使用一个递归调用而不是两个。放置枢轴后，您只需根据枢轴的位置为其中一个分区调用快速排序。这是 O(N ² )，但是 O(N) 的平均情况。如果你使用随机枢轴，它几乎总是 O(N)。