对于数组中的每个元素，我们如何计算右侧大于该元素的元素数？

Question

给定一个A具有 n 个值的数组，设XA 是一个数组，该数组在索引 i 中保存比A[i]原始数组中其右侧更大且位于其右侧的元素数A。

例如，如果 A 是：[10,12,8,17,3,24,19]，则 X(A) 是：[4,3,3,2,2,0,0]

如何在O(n log(n))时间和O(n)空间复杂度中解决这个问题？

我可以通过使用循环在O(n^2)Time and O(1)Space 中轻松解决这个问题，并且对于每个元素，计算右侧有多少元素比它大，但我没有成功满足这些要求。

我正在考虑使用快速排序O(n log(n))，最坏的情况是可以完成，但我不知道排序数组在这里有什么帮助。

注意：关于快速排序算法需要一些调整以确保 O(n log(n)) 在最坏情况下而不是平均情况下。

Answer 1

问题陈述的快速总结：给定一个A包含N整数的数组，构造一个数组X，使得对于 each i，X[i] =其中A索引大于i并且也大于的元素数A[i]。

解决这个问题的一种方法是使用二叉搜索树。首先从最后一个元素迭代到第一个元素，在迭代时将每个元素添加到集合中。每次我们在一个元素上时e，使用二叉搜索树的find()操作来查找比e当前树中的元素大多少。

也许您的第一个想法是使用 a std::multiset（不是std::set因为我们可能有重复元素！），这是一个自平衡二叉搜索树，提供O(logN)插入和O(logN)元素查找。这似乎适用于该算法，但实际上不会。原因是因为当你调用 时std::multiset::find()，它会返回一个迭代器到集合中的元素。查找集合中有多少元素实际上大于元素需要O(N)时间，因为查找从迭代器到集合末尾的距离需要重复递增。

为了解决这个问题，我们使用了一个“索引多重集”，它是一个稍微修改过的二叉搜索树，这样我们可以在仍然支持插入的同时及时找到多重集中元素的索引。这是我演示此数据结构的代码：O(logN)O(logN)

#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// I know this is kind of messy, but it's the general way to get a C++ indexed
// multiset without using an external library
typedef tree <int, null_type, less_equal <int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

int main()
{
    int A_size;
    cin >> A_size;

    vector <int> A(A_size);
    for(int i = 0; i < A_size; ++i){
        cin >> A[i];
    }
    // Input Done

    indexed_set nums;
    vector <int> X(A_size);
    for(int i = A_size - 1; i >= 0; --i){
        // order_of_key returns the first index that A[i] would be at in a sorted list
        // with the same elements as nums.
        X[i] = nums.size() - nums.order_of_key(A[i]);

        nums.insert(A[i]);
    }

    for(int item : X){
        cout << item << " ";
    }
    cout << "\n";

    return 0;
}

因此，总体而言，总体策略是

1. 从最后一个元素迭代到第一个元素。
2. 对于每个元素，签入nums以查看有多少元素大于当前元素。( O(logN))
3. 然后，插入当前元素并继续迭代。( O(logN)) 显然，该算法的总时间复杂度为O(NlogN)，空间复杂度为O(N)。

对这种方法的观察和见解的快速总结：

1. INSIGHT：如果我们从最后一个元素迭代到第一个元素（不是从第一个元素到最后一个元素），索引集将只包含在任何给定迭代中当前元素右侧的元素，这正是我们想要的。这节省了我们的时间，因为如果我们从左到右迭代，我们不需要担心在开始时插入所有元素然后一个一个删除它们。

2. 观察：Astd::set对于该算法中的二叉搜索树来说是不够的，因为尽管它提供了O(logN) 查找元素的功能，但计算集合中元素的位置需要最坏的O(N)时间情况。然而，索引集O(logN)及时提供了这种“定位”操作以及插入。

Answer 2

Telescope首先提到（在评论中）您可以使用二叉树来实现这一点。但是，您也可以使用以下替代方法来做到这一点：

1. 使用 AVL 树；
2. 每个节点应该在其右子树上存储元素和元素数量；
3. 从头到尾迭代数组；
4. 添加到树中并相应地更新节点上的大小。
5. 添加时将当前元素与根进行比较；如果此元素小于根，则它小于右子树的所有元素。在这种情况下，从该节点获取大小，然后继续到左子树并应用相同的逻辑。将最终的大小加到数组X上对应的位置；
6. 如果它不小于根，则增加根的大小并继续到适当的子树。并应用上述逻辑。

时间复杂度将是插入树的 N 次。因此，O(n log(n))。而且空间复杂度自然会高O(N)。

可视化：

答：[10,12,8,17,3,24,19];
X(A) [? ，？，？，？，？，？,?]
右树节点大小：S [?,?,?,?,?,?,?]

插入19：

因此，右子树中没有元素：

• 大小为 19 = 0；
• X(A) [? ，？，？，？，？，？,0]
  
• S [?, ?, ?, ?, ?, ?, 0]

插入24：

• 24 大于根（即19）所以让我们增加根的大小并继续子右树。
• 24 的大小 = 0
• X(A) [? ，？，？，？，？,0 ,0]
  
• S [?, ?, ?, ?, ?, 0, 1]

插入3：

• 3 小于根（即19）并且根的大小为 1，因此有 2 个元素大于 3 根及其右子树。让我们往左边走；
• 3 = 0 的大小
• X(A) [? ，？，？，？,2 ,0 ,0]
• [? , ?, ?, ?, 0, 0, 1]

插入17：

• 17 小于根（即19），根的大小为 1，因此有 2 个元素大于 17 根及其右子树。让我们向左走，17 比根（即3）大，让我们将节点 3 的大小从 0 增加到 1，然后转到右子树。
• 17 的大小 = 0
• X(A) [? ，？，？,2 ,2 ,0 ,0]
• [? ，？，？,0 ,1 ,0 ,1]

插入8：

• 8 小于根（即19），根的大小为 1，因此有 2 个元素大于 8 根及其右子树。让我们向左走，8 比根（即3）大，让我们将节点 3 的大小从 1 增加到 2，然后转到右子树。8 也小于根（即17），所以到目前为止 8 小于三个元素。让我们往左边走。
• 大小 8 = 0
• X(A) [? ，？,3 ,2 ,2 ,0 ,0]
• [? ，？,0 ,0 ,2 ,0 ,1]

随着节点8的插入，执行旋转以平衡树。

在旋转过程中，大小也会更新，即节点 8 的大小从 0 变为 1，节点 3 的大小从 2 变为 0。： - S [? ，？,1 ,0 ,0 ,0 ,1]

插入12：

• 12 小于根（即19），根的大小为 1，因此有 2 个元素大于 12 根及其右子树。让我们向左走，12 比根（即8）大，让我们将节点 8 的大小从 1 增加到 2，然后转到右子树。12 也小于根（即17），所以 12 到目前为止小到三个元素。让我们往左边走。

• 12 的大小 = 0

• X(A) [? ,3 ,3 ,2 ,2 ,0 ,0]

• [? ,0 ,0 ,0 ,2 ,0 ,1]

随着节点12的插入，执行双旋转以平衡树。

在旋转过程中，尺寸也会更新 - S [? ,0 ,1 ,2 ,0 ,0 ,1]

插入10：

• 10 小于根（即17）并且根的大小为 2，因此有 3 个元素大于 10 根及其右子树。让我们向左走，10 比根（即8）大，让我们将节点 8 的大小从 1 增加到 2，然后转到右子树。10 也小于根（即12），所以 10 到目前为止小于 4 个元素。让我们往左边走。

• 10 的大小 = 0
• X(A) [4 ,3 ,3 ,2 ,2 ,0 ,0]
• S [0 ,0 ,0 ,0 ,2 ,0 ,1]

一个可能的 C 实现（AVL 代码改编自source）：

#include<stdio.h>
#include<stdlib.h>
 
struct Node{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
    int size;
};
 
int height(struct Node *N){
    return (N == NULL) ? 0 : N->height;
}

int sizeRightTree(struct Node *N){
    return (N == NULL || N -> right == NULL) ? 0 : N->right->height;
}
 
int max(int a, int b){
    return (a > b) ? a : b;
}
 
struct Node* newNode(int key){
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;
    node->size = 0;
    return(node);
}
 
struct Node *rightRotate(struct Node *y) {
    struct Node *x = y->left;
    struct Node *T2 = x->right;
 
    x->right = y;
    y->left = T2;
 
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    y->size = sizeRightTree(y);
    x->size = sizeRightTree(x);
    return x;
}
 
struct Node *leftRotate(struct Node *x){
    struct Node *y = x->right;
    struct Node *T2 = y->left;
 
    y->left = x;
    x->right = T2;
 
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
    y->size = sizeRightTree(y);
    x->size = sizeRightTree(x); 

    return y;
}
 
int getBalance(struct Node *N){
    return (N == NULL) ? 0 : height(N->left) - height(N->right);
}
 
struct Node* insert(struct Node* node, int key, int *size){
    if (node == NULL)
        return(newNode(key));
    if (key < node->key){
        *size = *size + node->size + 1;
        node->left  = insert(node->left, key, size);
    } 
    else if (key > node->key){
    node->size++;
    node->right = insert(node->right, key, size);
    }
    else 
        return node;
 
    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);
 
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    if (balance > 1 && key > node->left->key){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    } 
    return node;
}

int main()
{
  int arraySize = 7;
  struct Node *root = NULL;
  int A[7] = {10,12,8,17,3,24,19};
  int X[7] ={0};
  for(int i = arraySize - 1; i >= 0; i--)
     root = insert(root, A[i], &X[i]);

  for(int i = 0; i < arraySize; i++)
     printf("%d ", X[i]);
  printf("\n");
  return 0;
}

输出：

4 3 3 2 2 0 0