给定的阵列，对于每个元件，找出元素比它更低，这似乎它的右侧的总数 [英] given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it

问题描述

我previously发布了一个问题，<一个href="http://stackoverflow.com/questions/9493853/given-an-array-find-out-the-next-minimum-element-for-each-element">given的阵列，找出每个元素的下一个最小单元的 现在，我是想知道，是否有办法找出给定的数组，对每个元素，找出元素比它更小，这似乎它的右侧总数 例如，阵列[4 2 1 5 3]应该产生[3 1 0 1 0] ...

I had previously posted a question, given an array, find out the next minimum element for each element now, i was trying to know , if there is any way to find out "given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it" for example, the array [4 2 1 5 3] should yield [3 1 0 1 0]??

我已经研究出了解决办法，请看看它，并让我知道是否有任何错误。

I have worked out a solution, please have a look at it, and let me know if there is any mistake.

1做一个平衡BST插入元素遍历从右数组至左

1 Make a balanced BST inserting elements traversing the array from right to left

2的BST是在这样一种方式，每个元素保存基于有元素树的大小

2 The BST is made in such a way that each element holds the size of the tree rooted at that element

3现在当你寻找合适的位置插入任何元素，取子树的根在左侧的兄弟+ 1（父）总规模的帐户，如果你向右移动 现在，因为，计数正在计算在插入的元件的时间，并且，我们正从从右向左移动，我们得到比给定的元件出现后它元件更低的准确计数。

3 Now while you search for the right position to insert any element, take account of the total size of the subtree rooted at left sibling + 1(for parent) if you move right Now since, the count is being calculated at the time of insertion of an element, and that we are moving from right to left, we get the exact count of elements lesser than the given element appearing after it.

推荐答案

它可以在O解决（N log n）的。

It can be solved in O(n log n).

如果在一个BST您存储基于有节点搜索时的节点（到达从根）可以算元件更大的数目的子树的元素数/小于在路径较小：

If in a BST you store the number of elements of the subtree rooted at that node when you search the node (reaching that from the root) you can count number of elements larger/smaller than that in the path:

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)
}

**例如，如果<一个href="http://www.wolframalpha.com/share/img?i=d41d8cd98f00b204e9800998ecf8427ehj2gv3kiu7&f=HBQTQYZYGY4TOM3BMJSTAMJQGEYDCM3BMJTDMNTCMZSDSMBQG44Qaaaa"相对=nofollow>这是我们的树，我们正在寻找的关键3，count_larger会呼吁：

** for example if this is our tree and we're searching for key 3, count_larger will be called for:

- >（节点2,3，0）
- >（节点4，3,0）
--->（节点3,3，2）

-> (node 2, 3, 0)
--> (node 4, 3, 0)
---> (node 3, 3, 2)

和最终的答案是2预期。

and the final answer would be 2 as expected.

这篇关于给定的阵列，对于每个元件，找出元素比它更低，这似乎它的右侧的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！