algorithm - 将数组转换为中位数数组

Question

我正在考虑以下问题的解决方案:我有一个很大的整数数组(在更棘手的情况下是一个整数流)，我想将该数组转换为中位数数组，它的位置是否对应于中位数数组 [0..i]。

现在，我的蛮力方法是对每个子数组进行排序，然后选择中间元素。即 O(n^2 log n)，因为每个 n 子数组必须在 N log N 时间内排序。我可能可以使用某种计数机制将时间减少到 N^2，但是 N^2 是可以做到的最好的吗？

Answer 1

将单个项目插入到已排序的树状结构中，例如一棵红黑树，需要 O(log n)。如果您维护每个节点的后代数量，那么也可以在 O(log n) 中找到中位数。对流中的所有 n 元素执行此操作，并且您有一个 O(n log n) 算法。

数据结构和中值计算看起来像这样:

struct TreeNode {
  enum { RED, BLACK } color;
  size_t numElements;
  int value;
  TreeNode* left, right;
} *root;

TreeNode* treeSelect(TreeNode *top, size_t count) {
  if (top->left != NULL) {
    if (count < top->left->numElements)
      return treeSelect(top->left, count)
    count -= top->left->numElements;
  }
  if (count == 0)
    return top;
  return treeSelect(top->right, count - 1);
}

TreeNode* treeMedian() {
  return treeSelect(root, root->numElements / 2);
}

其他操作是那些通常用于红黑树的操作，尽管您可以跳过那些删除节点的操作。您可以调整它们以处理重复元素。这里的一般规则是，当要插入的元素等于当前节点的元素时，可以插入到任何子树中。并且在平衡树时，应该保持重复键的顺序，这样您也可以保持附加子树的顺序。但是除非我遗漏了什么，否则在任何情况下平衡都会在没有值(value)比较的情况下起作用，所以一旦你插入了重复项，你就完成了。如果您期望确实有很多重复值，则可以改用类似多图的方法，在每个节点中使用一个计数器。