algorithm - 数组中每个位置左侧不同的较小元素的数量

Question

我偶然发现了找到左侧不同元素的数量并且小于数组中每个位置的元素的问题。

示例：

对于数组1 1 2 4 5 3 6，答案是0 0 1 2 3 2 5

在 O(n ² ) 中解决问题很简单，我想知道问题是否可以在 O(n*lg(n)) 中解决。

Answer 1

是的，您可以将元素插入到平衡（红黑、AVG 等）二叉搜索树中，将子树节点总数存储在每个节点中。更新是 O(log N)，因为您只更新到根的路径，并且检查不同元素的数量也是 O(log N)，因为它需要对从新元素到的路径上的左子树的节点数求和根。

这是插入 [0,1,2,3,5,6] 后的树的样子，括号中的子树节点数。

    2(6)
   /  \
  1(2) 5(3)
 /    / \
0(1) 3(1)6(1)

在插入 6（假设它是最后一个）时，您添加：

• 2（左子树的节点数为 2）
• 1（带2的节点，因为你走对路，所以root更小）
• 1（5的左子树）
• 1（5的节点，同理，没有左子树要添加）

总计 5。树有点太小，看不到保留总计的节省，但请注意，您不需要访问 0 节点，它在其父节点 - 1 节点中进行了说明。