给定一个数组,对于每个元素,找出小于它的元素总数,它们显示在它的右边

Question

我之前发过一个问题,给定一个数组,现在找出每个元素的下一个较小的元素 ,我试图知道,如果有任何方法可以找出"给定一个数组,对于每个元素,找出总数比它更小的元素,它出现在它的右边"例如,数组[4 2 1 5 3]应该产生[3 1 0 1 0] ??

[编辑]我已经找到了解决方案,请看一下,如果有任何错误,请告诉我.

1制作一个平衡的BST插入元素,从右到左穿过阵列

2 BST的制作方式使每个元素都保持以该元素为根的树的大小

3现在,当您搜索插入任何元素的正确位置时,如果向右移动,请考虑根据左侧兄弟+ 1(对于父级)生成的子树的总大小,因为计数是在插入时计算的一个元素,并且我们从右向左移动,我们得到的元素的精确数量小于它后面出现的给定元素.

Answer 1

它可以用O(n log n)求解.

如果在BST中存储了在搜索节点时从该节点生根的子树的元素数(从根节点到达),则可以计算大于/小于路径中元素的元素数:

int count_larger(node *T, int key, int current_larger){
    if (*T == nil)
        return -1;
    if (T->key == key)
        return current_larger + (T->right_child->size);
    if (T->key > key)
        return count_larger(T->left_child, key, current_larger + (T->right_child->size) + 1);
    return count_larger(T->right_child, key, current_larger)
}

**例如,如果这是我们的树并且我们正在搜索键3,则将调用count_larger:

- >(节点2,3,0)
- >(节点4,3,0)
--->(节点3,3,2)

最终的答案是预期的2.