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

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),因为您只沿​​着root的路径更新,并且检查不同元素的数量也是O(log N),因为它需要将从新元素到的路径上的左子树的nodecount相加根.

这是插入[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节点中占用.