1

我正在思考以下问题的解决方案：我有一个大整数数组（在更难的情况下是整数流），我想将该数组转换为中位数数组，即它的位置对应于数组的中位数 [ 0..i]。

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

4

3 回答 3

3

将单个项目插入到已经排序的树状结构中，例如红黑树，将花费 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);
}

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

于 2013-01-11T11:56:43.580 回答
0

可以通过O(nlogn)以下方法完成：

使用跳过列表（或 B+ 树）来维护数据流。
还要维护一个指向当前中位数的指针。

在每次迭代中，让节点数为n（在插入刚到达的元素之前），中位数（值）为m，您看到的新值为x。

  1. 插入x跳过列表
  2. if n%2 ==0(中位数的索引应该增加):
    if x < m.value: 不需要改变, 的索引m也增加
    else: setm <- m.next
  3. else: (中位数的索引应该保持不变)
    if x < m.value: set m <- m.previous//因为 m 的索引增加了
    else: 不需要更改。//m的索引没有增加
  4. m.value是下一个元素的中位数

找到上一个/下一个是O(1)，插入x是O(logn)- 总复杂度是O(nlogn)额外的O(n)空间。

注意：如果流可以包含重复元素，则应特别注意，并且跳过列表应具有确定性行为 - 即始终插入最后一个可能的索引

于 2013-01-11T12:00:41.917 回答
0

使用一些快速的 BST，如 AVL 或 Splay。您可以简单地修改结构，以便每个节点都能及时获得其子树的中值log N。特别是您可以获得树中所有项目的中位数。

现在你正在做这样的事情：

Create empty BST
foreach n in stream:
    Insert n to BST
    Get median from BST.root
于 2013-01-11T12:31:40.607 回答