破解编码面试第6版:10.10.从流中排名

Question

问题陈述如下：

假设您正在整数流中读取。定期，你 希望能够查找数字 x 的排名(数字 小于或等于 x 的值)。实现数据结构和 支持这些操作的算法。也就是说，实现方法 跟踪(在 T X 中)，在生成每个数字时调用，以及 方法 getRankOfNumber(int x) ，它返回值的数量 小于或等于 X(不包括 x 本身)。

示例：流(按出现顺序)：5， 1， 4， 4， 5， 9， 7， 13， 3

getRankOfNumber(1) = 0 getRankOfNumber(3) =1 getRankOfNumber(4) = 3

建议的解决方案使用修改后的二叉搜索树，其中每个节点存储该节点左侧的节点数。两种方法的时间复杂度对于平衡树为 O(logN)，对于不平衡树为 O(N)，其中 N 是节点数。

但是我们如何从随机整数流中构建平衡的 BST？如果我们继续添加到同一棵树并且根不是中位数，树不会在适当的时候变得不平衡吗？对于这个解决方案，最坏的情况复杂性不应该是O(N)吗(在这种情况下，分别用于track()和getRankOfNumber()的O(1)和O(N)的HashMap会更好)？

Answer 1

你只需要建立一个AVL或红黑树，以获得你想要的O(lg n)复杂性。

关于等级，它有点简单。我们调用 count(T) 根为 T 的树的元素数。

• 节点 N 的等级将为：
  • 首先在 N 之前会有count(N's left subtree)个节点(小于 N 的元素)
  • 让 A = N 的父亲。如果 N 是 A 的右子，那么在 N 之前会有1 + count(A's left subtree)个节点
  • 如果 A 是某个 B 的右子，那么在 N 之前会有1 + count(B's left subtree)个节点
  • 递归地，一直向上运行，直到你到达根或直到你所在的节点不是某人的右儿子。

由于平衡树的高度最多为 lg(n)，此方法将采用 O(lg n) 返回某人的秩(O(lg n)查找 + O(lg n) 跑回并测量等级)，但这考虑到所有节点都存储其左右子树的大小。

希望对:)有所帮助

Answer 2

使用数字流构建二叉搜索树(BST)应该更容易想象。所有小于节点的值都向左移动，所有大于节点的值向右移动。 然后，任何 x 的排名将是该节点的左侧子树中值为 x 的节点数。

要完成的操作：查找值 x O(logN) + 计数的节点 找到的节点的子树 O(logN) = 总 O(logN+ logN) = O(logN)

为了优化从O(logN)到O(1)的左子树节点计数的搜索，您可以在Node类中保留另一个类变量'leftSubTreeSize'，并在插入节点时填充它。