查找未排序数组中多个子数组的中位数

Question

假设给定一个未排序的整数数组 S 和 T 中的范围列表，请返回每个范围的中位数列表。

例如，S = [3,6,1,5,0,0,1,-2]，T = [[1,3],[0,5],[4,4]]。返回 [5, 2, 0]。

有没有比在每个范围上运行中位数更好的方法？我们可以以某种方式预先计算/缓存结果吗？

Answer 1

让我向您介绍一个有趣的数据结构，称为小波树：

\n\n

您可以通过查看整数的位串表示并递归地平分它们来构建它：

\n\n

首先将整数分为最高有效位 (MSB) 0 和 MSB 1。但是，您可以将 MSB 按其原始顺序存储在位向量中。然后，对于每个整数子集，您忽略 MSB 并针对下一个最高有效位递归地重复此构造。

\n\n

如果重复此操作直至最低有效位，您将得到如下的树结构（请注意，索引仅用于说明，您应该仅存储位向量）：

\n\n

\n\n

您可以很容易地看到，构建此数据结构需要 O(n log N) 时间，其中 n 是整数的数量，N 是它们的最大值。

\n\n

小波树有一个很好的特性，它们同时表示原始序列及其排序后的对应序列：

\n\n

\n

• 如果读取最上面的位向量，您将获得输入序列的 MSB。要重建条目的下一位，您可以交替查看根的左子节点（如果 MSB 为 0）或右子节点（如果 MSB 为 1）的位向量。对于以下位，您可以递归地继续。

\n

• 如果从左到右读取叶节点，就会得到排序序列。

\n

\n\n

为了有效地使用小波树，您需要对位向量进行两个基本操作：

\n\n

\n
• rank1(k)告诉您位向量中第k个位置之前有多少个 1 ， rank0对 0 执行相同的操作
\n
• select1(k)告诉您位向量中第k个 1的索引， select0对 0 执行相同的操作
\n

\n\n

请注意，有些位向量表示仅需要 o(n)（小 o）位的额外存储来在 O(1) 中实现这些操作

\n\n

您可以按如下方式使用它们：

\n\n

\n

• 如果您查看上面序列中的前 7 个，它的索引为 3。如果您现在想知道它在右子节点中的索引，只需在根位向量上调用rank1(3)并得到 2，即正好是右子节点中前 7 个的索引

\n

• 如果您位于包含 4544 的子节点，并且想要知道包含 46754476 的父节点中第二个 4（索引为 2）的位置，则可以对父节点的位向量调用select0(2)并获取索引 5。

\n

\n\n

现在如何用它来实现范围中值查询？您需要实现的最重要的认识是，找到大小为k的范围的中值相当于选择第k/2个元素。

\n\n

该算法的基本思想类似于快速选择：将元素范围一分为二，并仅递归到包含要查找的元素的范围。

\n\n

假设我们想要找到从第二个 2（含）开始到 1（不包括）结束的范围的中位数。\n这些元素有 7 个，因此中位数的排名为 4（第四小的元素）现在，在该范围的开头和结尾的根位向量中使用rank0/1调用，我们在根的子代中找到相应的范围：

\n\n

\n\n

正如您所看到的，左侧范围（仅包含较小的元素）只有 3 个元素，因此排名为 4 的元素必须包含在根的右子元素中。4 - 3 = 1我们现在可以递归地搜索右子元素中具有排名的元素。通过递归地下降小波树直到到达叶子，您可以在小波树的每个级别仅使用两次排序操作（\xc3\xa0 O(1) 时间）来识别中值，因此整个范围中值查询需要 O( log N) 时间，其中 N 是输入序列中的最大数字。

\n\n

如果您想了解这些小波树的实际实现，请查看简洁数据结构库 (SDSL)，它实现了上述位向量和不同的小波变换变体。

\n