对于数组中的每个元素，我们如何计算右边大于该元素的元素数？
How can we calculate, for every element in an array, the number of elements to the right that are greater than that element?
给定一个有 n 个值的数组 A，让 A 的 X 是一个数组，它在索引 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) Space 复杂度内解决这个问题？
我可以在 O(n^2) 时间和 O(1) Space 中轻松解决这个问题，方法是使用循环，对于每个元素，计算右侧有多少元素比它大，但我没有成功满足这些要求。
我正在考虑使用快速排序，最坏情况下可以在 O(n log(n)) 中完成，但我看不出排序数组在这里有什么帮助。
注意：关于快速排序，算法需要进行一些调整以确保在最坏情况下而非仅在平均情况下为 O(n log(n))。
Telescope 首先提到（在评论中）您可以使用二叉树来实现这一点。但是，您也可以使用以下替代方法来完成此操作：
- 使用AVL树；
- 每个节点都应该存储其右子树上的元素和元素个数；
- 从头到尾遍历数组；
- 添加到树中并相应地更新节点的大小。
- 添加时将当前元素与根进行比较；如果此元素小于根，则它小于右子树的所有元素。在这种情况下，从该节点获取大小，然后继续到左子树并应用相同的逻辑。将最终大小添加到数组X上的对应位置；
- 如果它不小于根则增加根的大小并继续到适当的子树。并应用上述逻辑。
插入树的时间复杂度为N次。因此，O(n log(n))。 space 的复杂度自然是 O(N).
可视化：
A : [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]
- S[? , ?, ?, ?, 0, 0, 1]
正在插入 17:
- 17小于根（即19），根的大小为1，因此有2个元素大于17根及其右子树。让我们往左走，17比根大（即, 3），让我们把节点3的大小从0增加到1，然后走到右子树.
- 17 的大小 = 0
- X(A)[? ,? ,? ,2 ,2 ,0 ,0]
- S[? ,? ,? ,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]
- S[? ,? ,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]
S[? ,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
问题陈述的快速总结：给定一个包含 N 个整数的数组 A，构造一个数组 X，使得每个 i、X[i] = A 中索引大于 i 且也大于 A[i].
的元素数
解决这个问题的一种方法是使用二叉搜索树。从最后一个元素迭代到第一个元素开始，在迭代时将每个元素添加到集合中。每次我们在一个元素e处，使用二叉搜索树的find()运算，查找当前树中有多少个元素大于e。
也许您的第一个想法是使用 std::multiset（不是 std::set，因为我们可能有重复的元素！），这是一个自平衡二叉搜索树，它提供 O(logN) 插入和 O(logN) 元素查找。这似乎适用于该算法，但实际上不会。原因是因为当您调用 std::multiset::find() 时，它 returns 是集合中元素的迭代器。查找集合中有多少元素实际上 比该元素大 需要 O(N) 时间，因为查找从迭代器到集合末尾的距离需要递增它反复。
为了解决这个问题，我们使用了一个“索引多重集”，它是一个稍微修改过的二叉搜索树，这样我们就可以在多重集中找到一个元素的 index 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;
}
所以，总的来说，一般的策略是
- 从最后一个元素迭代到第一个元素。
- 对于每个元素，检查
nums 以查看有多少元素大于当前元素。 (O(logN))
- 然后，插入当前元素，继续迭代。 (
O(logN))
显然，该算法的总时间复杂度为O(NlogN)，space复杂度为O(N).
对该方法的观察和见解的快速总结：
洞察力：如果我们从最后一个元素迭代到第一个元素（而不是第一个元素到最后一个），索引集将只包含在任何给定迭代中当前元素右侧的元素，这正是我们想要的。这节省了我们的时间，因为如果我们要从左到右迭代，我们不需要担心在开始时插入所有元素然后一个一个地删除它们。
观察：std::set 不足以满足此算法中的二叉搜索树，因为尽管它提供了 O(logN) 发现 一个元素，计算set中的元素position需要最坏情况O(N)的时间。然而，索引集在 O(logN) 时间内提供这种“定位”操作以及插入。
类似于合并排序，其中在处理右侧和处理范围左侧之前插入计数，例如：
#include <algorithm>
#include <functional>
void count_greater_on_right( int* a, int* x, int begin, int end )
{
if( end - begin <= 2 )
{
if( end - begin == 2 && a[begin] < a[begin+1] )
{
x[begin]+=1; // specific
std::swap( a[begin], a[begin+1] );
}
return;
}
int middle =(begin+end+1)/2;
count_greater_on_right( a, x, middle, end );
// specific
{
for( int i=begin; i!=middle; ++i )
{
x[i]+=std::lower_bound( &a[middle], &a[end], a[i], std::greater<int>() )-&a[middle];
}
}
count_greater_on_right( a, x, begin, middle );
std::inplace_merge( &a[begin], &a[middle], &a[end], std::greater<int>() );
}
任务特定的代码，注释为// specific;
排序的相反顺序使恕我直言稍微简单一些；
更新 'a' 因此，如果您需要原始序列，请创建副本。
如果将数组分成子范围，然后对这些子范围进行排序，问题就可以解决。详细来看，
给定数组 = [10, 12, 8, 17, 3, 24, 19]
现在将数组划分为长度 4 的子范围，并对这些子范围进行排序，如下所示，
子范围排序数组
.................... ...............
| 8 | 10 | 12 | 17 | | 3 | 19 | 24 |
.................... ...............
2 0 1 3 4 6 5 => index
让我们获取子范围排序数组的第一个条目 8 并尝试找到大于 8
的正确元素数
正如您在上面的数字 8 中看到的，属于第一个子范围，并且由于子范围已排序，因此子范围中的元素按升序排列但不按索引顺序排列。这意味着在当前子范围内，我们必须将元素 8 右侧的所有元素的索引与元素 8
的索引进行比较
8 的索引是 2 但 10 有 index = 0，这意味着 10 在输入数组中 8 的左边,
12 的索引也小于 8 的索引，这意味着 12 在输入数组中 8 的左侧，
17的索引是3，它大于8的索引，这意味着17在输入数组中8的右边，可以认为更大元素，
将8的索引与当前子范围右大元素count = 1所有右边元素的索引进行比较后，再看下一个范围
在8的子范围之后，事情完全变了，现在我们知道这个子范围在子范围元素8所属的右边，这意味着我们不必比较8的索引和元素或者这个范围，都在元素8的右边，我们只需要找出有多少大于8，
现在我们将右子范围的第一个元素与 8 进行比较，正如您在上面看到的，第一个元素是 3，它小于 8，但是如果第一个元素是 8右子范围大于当前元素然后我们可以将计数直接增加到右子范围中存在的元素数。
因为第一个元素 3 小于 8 我们在右子范围内找到 8 的上限，即 19 和 [= 中的所有元素右子范围中的 47=] 大于 8，因此有两个元素 19, 24 并且由于此计数递增 two 并变为 count = 3
最后有 3 个大于元素 8.
的右边元素
以类似的方式，可以为所有元素找到更多右边元素的数量，结果数组将是，
x(A) = [4, 3, 3, 2, 2, 0, 0]
结论是，通过将输入数组划分为已排序的子范围，可以通过以下步骤找到右边更大的元素，
- 比较当前子范围所有正确元素的索引，
- 比较右子范围的第一个元素，如果，
一世。第一个元素大于当前元素，右范围内的所有元素都大于当前元素，
二.第一个元素小于，然后在右子范围内找到当前元素的上界，右子范围上界的元素大于当前元素。
- 对所有正确的子范围重复步骤 2。
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using std::cout;
std::vector<std::pair<int, std::size_t>> arrayOfSortedSubRange(std::size_t subRangeSize,
const std::vector<int>& numArr){
std::vector<std::pair<int, std::size_t>> res;
res.reserve(numArr.size());
for(std::size_t i = 0, numArrSize = numArr.size(); i < numArrSize; ++i){
res.emplace_back(numArr[i], i);
}
for(std::vector<std::pair<int, std::size_t>>::iterator it = res.begin(), endIt = res.end(); endIt != it;){
std::vector<std::pair<int, std::size_t>>::iterator rangeEndIt = it + std::min<std::ptrdiff_t>(endIt - it,
subRangeSize);
std::sort(it, rangeEndIt, [](const std::pair<int, std::size_t>& a, const std::pair<int, std::size_t>& b){
return a.first < b.first;});
it = rangeEndIt;
}
return res;
}
std::size_t rightGreterElmentCountOfNumber(int num, std::vector<std::pair<int, std::size_t>>::const_iterator rightSubRangeIt,
std::vector<std::pair<int, std::size_t>>::const_iterator endIt){
std::size_t count = 0;
std::vector<std::pair<int, std::size_t>>::const_iterator subRangEndIt = rightSubRangeIt +
std::min<std::ptrdiff_t>(endIt - rightSubRangeIt, 4);
while(endIt != rightSubRangeIt){
if(rightSubRangeIt->first > num){
count += subRangEndIt - rightSubRangeIt;
}
else{
count += subRangEndIt -
std::upper_bound(rightSubRangeIt, subRangEndIt, num, [](int num,
const std::pair<int, std::size_t>& element){ return num < element.first;});
}
rightSubRangeIt = subRangEndIt;
subRangEndIt += std::min<std::ptrdiff_t>(endIt - subRangEndIt, 4);
}
return count;
}
std::vector<std::size_t> rightGreaterElementCountForLessThanFiveNumbers(const std::vector<int>& numArr){
std::vector<std::size_t> res(numArr.size(), 0);
std::vector<std::size_t>::iterator resIt = res.begin();
for(std::vector<int>::const_iterator it = numArr.cbegin(), lastIt = it + (numArr.size() - 1); lastIt != it;
++it, ++resIt){
*resIt = std::count_if(it + 1, numArr.cend(), [num = *it](int rightNum){return rightNum > num;});
}
return res;
}
std::vector<std::size_t> rightGreaterElementCount(const std::vector<int>& numArr){
if(numArr.size() < 5){
return rightGreaterElementCountForLessThanFiveNumbers(numArr);
}
std::vector<std::size_t> resArr(numArr.size(), 0);
std::vector<std::pair<int, std::size_t>> subRangeSortedArr = arrayOfSortedSubRange(4, numArr);
for(std::vector<std::pair<int, std::size_t>>::const_iterator it = subRangeSortedArr.cbegin(),
endIt = subRangeSortedArr.cend(); endIt != it;){
std::vector<std::pair<int, std::size_t>>::const_iterator rightNextSubRangeIt = it + std::min<std::ptrdiff_t>(
endIt - it, 4);
for(std::vector<std::pair<int, std::size_t>>::const_iterator eleIt = it; rightNextSubRangeIt != eleIt; ++eleIt){
std::size_t count = std::count_if(eleIt, rightNextSubRangeIt, [index = eleIt->second](
const std::pair<int, std::size_t>& element){ return index < element.second;});
if(endIt != rightNextSubRangeIt){
count += rightGreterElmentCountOfNumber(eleIt->first, rightNextSubRangeIt, endIt);
}
resArr[eleIt->second] = count;
}
it += std::min<std::ptrdiff_t>(endIt - it, 4);
}
return resArr;
}
int main(){
std::vector<std::size_t> res = rightGreaterElementCount({10, 12, 8, 17, 3, 24, 19});
cout<< "[10, 12, 8, 17, 3, 24, 19] => [";
std::copy(res.cbegin(), res.cbegin() + (res.size() - 1), std::ostream_iterator<std::size_t>(cout, ", "));
cout<< res.back()<< "]\n";
}
输出：
[10, 12, 8, 17, 3, 24, 19] => [4, 3, 3, 2, 2, 0, 0]
给定一个有 n 个值的数组 A，让 A 的 X 是一个数组，它在索引 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) Space 复杂度内解决这个问题？
我可以在 O(n^2) 时间和 O(1) Space 中轻松解决这个问题，方法是使用循环，对于每个元素，计算右侧有多少元素比它大，但我没有成功满足这些要求。
我正在考虑使用快速排序，最坏情况下可以在 O(n log(n)) 中完成，但我看不出排序数组在这里有什么帮助。
注意：关于快速排序，算法需要进行一些调整以确保在最坏情况下而非仅在平均情况下为 O(n log(n))。
Telescope 首先提到（在评论中）您可以使用二叉树来实现这一点。但是，您也可以使用以下替代方法来完成此操作：
- 使用AVL树；
- 每个节点都应该存储其右子树上的元素和元素个数；
- 从头到尾遍历数组；
- 添加到树中并相应地更新节点的大小。
- 添加时将当前元素与根进行比较；如果此元素小于根，则它小于右子树的所有元素。在这种情况下，从该节点获取大小，然后继续到左子树并应用相同的逻辑。将最终大小添加到数组X上的对应位置；
- 如果它不小于根则增加根的大小并继续到适当的子树。并应用上述逻辑。
插入树的时间复杂度为N次。因此，O(n log(n))。 space 的复杂度自然是 O(N).
可视化：
A : [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]
- S[? , ?, ?, ?, 0, 0, 1]
正在插入 17:
- 17小于根（即19），根的大小为1，因此有2个元素大于17根及其右子树。让我们往左走，17比根大（即, 3），让我们把节点3的大小从0增加到1，然后走到右子树.
- 17 的大小 = 0
- X(A)[? ,? ,? ,2 ,2 ,0 ,0]
- S[? ,? ,? ,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]
- S[? ,? ,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]
S[? ,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
问题陈述的快速总结：给定一个包含 N 个整数的数组 A，构造一个数组 X，使得每个 i、X[i] = A 中索引大于 i 且也大于 A[i].
解决这个问题的一种方法是使用二叉搜索树。从最后一个元素迭代到第一个元素开始，在迭代时将每个元素添加到集合中。每次我们在一个元素e处，使用二叉搜索树的find()运算，查找当前树中有多少个元素大于e。
也许您的第一个想法是使用 std::multiset（不是 std::set，因为我们可能有重复的元素！），这是一个自平衡二叉搜索树，它提供 O(logN) 插入和 O(logN) 元素查找。这似乎适用于该算法，但实际上不会。原因是因为当您调用 std::multiset::find() 时，它 returns 是集合中元素的迭代器。查找集合中有多少元素实际上 比该元素大 需要 O(N) 时间，因为查找从迭代器到集合末尾的距离需要递增它反复。
为了解决这个问题，我们使用了一个“索引多重集”，它是一个稍微修改过的二叉搜索树，这样我们就可以在多重集中找到一个元素的 index 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;
}
所以，总的来说，一般的策略是
- 从最后一个元素迭代到第一个元素。
- 对于每个元素，检查
nums以查看有多少元素大于当前元素。 (O(logN)) - 然后，插入当前元素，继续迭代。 (
O(logN)) 显然，该算法的总时间复杂度为O(NlogN)，space复杂度为O(N).
对该方法的观察和见解的快速总结：
洞察力：如果我们从最后一个元素迭代到第一个元素（而不是第一个元素到最后一个），索引集将只包含在任何给定迭代中当前元素右侧的元素，这正是我们想要的。这节省了我们的时间，因为如果我们要从左到右迭代，我们不需要担心在开始时插入所有元素然后一个一个地删除它们。
观察：
std::set不足以满足此算法中的二叉搜索树，因为尽管它提供了O(logN)发现 一个元素，计算set中的元素position需要最坏情况O(N)的时间。然而，索引集在O(logN)时间内提供这种“定位”操作以及插入。
类似于合并排序，其中在处理右侧和处理范围左侧之前插入计数，例如：
#include <algorithm>
#include <functional>
void count_greater_on_right( int* a, int* x, int begin, int end )
{
if( end - begin <= 2 )
{
if( end - begin == 2 && a[begin] < a[begin+1] )
{
x[begin]+=1; // specific
std::swap( a[begin], a[begin+1] );
}
return;
}
int middle =(begin+end+1)/2;
count_greater_on_right( a, x, middle, end );
// specific
{
for( int i=begin; i!=middle; ++i )
{
x[i]+=std::lower_bound( &a[middle], &a[end], a[i], std::greater<int>() )-&a[middle];
}
}
count_greater_on_right( a, x, begin, middle );
std::inplace_merge( &a[begin], &a[middle], &a[end], std::greater<int>() );
}
任务特定的代码，注释为// specific; 排序的相反顺序使恕我直言稍微简单一些； 更新 'a' 因此，如果您需要原始序列，请创建副本。
如果将数组分成子范围，然后对这些子范围进行排序，问题就可以解决。详细来看，
给定数组 = [10, 12, 8, 17, 3, 24, 19]
现在将数组划分为长度 4 的子范围，并对这些子范围进行排序，如下所示，
子范围排序数组
.................... ...............
| 8 | 10 | 12 | 17 | | 3 | 19 | 24 |
.................... ...............
2 0 1 3 4 6 5 => index
让我们获取子范围排序数组的第一个条目 8 并尝试找到大于 8
的正确元素数
正如您在上面的数字 8 中看到的，属于第一个子范围，并且由于子范围已排序，因此子范围中的元素按升序排列但不按索引顺序排列。这意味着在当前子范围内，我们必须将元素 8 右侧的所有元素的索引与元素 8
8 的索引是 2 但 10 有 index = 0，这意味着 10 在输入数组中 8 的左边,
12 的索引也小于 8 的索引，这意味着 12 在输入数组中 8 的左侧，
17的索引是3，它大于8的索引，这意味着17在输入数组中8的右边，可以认为更大元素，
将8的索引与当前子范围右大元素count = 1所有右边元素的索引进行比较后，再看下一个范围
在8的子范围之后，事情完全变了，现在我们知道这个子范围在子范围元素8所属的右边，这意味着我们不必比较8的索引和元素或者这个范围，都在元素8的右边，我们只需要找出有多少大于8，
现在我们将右子范围的第一个元素与 8 进行比较，正如您在上面看到的，第一个元素是 3，它小于 8，但是如果第一个元素是 8右子范围大于当前元素然后我们可以将计数直接增加到右子范围中存在的元素数。
因为第一个元素 3 小于 8 我们在右子范围内找到 8 的上限，即 19 和 [= 中的所有元素右子范围中的 47=] 大于 8，因此有两个元素 19, 24 并且由于此计数递增 two 并变为 count = 3
最后有 3 个大于元素 8.
以类似的方式，可以为所有元素找到更多右边元素的数量，结果数组将是，
x(A) = [4, 3, 3, 2, 2, 0, 0]
结论是，通过将输入数组划分为已排序的子范围，可以通过以下步骤找到右边更大的元素，
- 比较当前子范围所有正确元素的索引，
- 比较右子范围的第一个元素，如果，
一世。第一个元素大于当前元素，右范围内的所有元素都大于当前元素，
二.第一个元素小于，然后在右子范围内找到当前元素的上界，右子范围上界的元素大于当前元素。 - 对所有正确的子范围重复步骤 2。
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using std::cout;
std::vector<std::pair<int, std::size_t>> arrayOfSortedSubRange(std::size_t subRangeSize,
const std::vector<int>& numArr){
std::vector<std::pair<int, std::size_t>> res;
res.reserve(numArr.size());
for(std::size_t i = 0, numArrSize = numArr.size(); i < numArrSize; ++i){
res.emplace_back(numArr[i], i);
}
for(std::vector<std::pair<int, std::size_t>>::iterator it = res.begin(), endIt = res.end(); endIt != it;){
std::vector<std::pair<int, std::size_t>>::iterator rangeEndIt = it + std::min<std::ptrdiff_t>(endIt - it,
subRangeSize);
std::sort(it, rangeEndIt, [](const std::pair<int, std::size_t>& a, const std::pair<int, std::size_t>& b){
return a.first < b.first;});
it = rangeEndIt;
}
return res;
}
std::size_t rightGreterElmentCountOfNumber(int num, std::vector<std::pair<int, std::size_t>>::const_iterator rightSubRangeIt,
std::vector<std::pair<int, std::size_t>>::const_iterator endIt){
std::size_t count = 0;
std::vector<std::pair<int, std::size_t>>::const_iterator subRangEndIt = rightSubRangeIt +
std::min<std::ptrdiff_t>(endIt - rightSubRangeIt, 4);
while(endIt != rightSubRangeIt){
if(rightSubRangeIt->first > num){
count += subRangEndIt - rightSubRangeIt;
}
else{
count += subRangEndIt -
std::upper_bound(rightSubRangeIt, subRangEndIt, num, [](int num,
const std::pair<int, std::size_t>& element){ return num < element.first;});
}
rightSubRangeIt = subRangEndIt;
subRangEndIt += std::min<std::ptrdiff_t>(endIt - subRangEndIt, 4);
}
return count;
}
std::vector<std::size_t> rightGreaterElementCountForLessThanFiveNumbers(const std::vector<int>& numArr){
std::vector<std::size_t> res(numArr.size(), 0);
std::vector<std::size_t>::iterator resIt = res.begin();
for(std::vector<int>::const_iterator it = numArr.cbegin(), lastIt = it + (numArr.size() - 1); lastIt != it;
++it, ++resIt){
*resIt = std::count_if(it + 1, numArr.cend(), [num = *it](int rightNum){return rightNum > num;});
}
return res;
}
std::vector<std::size_t> rightGreaterElementCount(const std::vector<int>& numArr){
if(numArr.size() < 5){
return rightGreaterElementCountForLessThanFiveNumbers(numArr);
}
std::vector<std::size_t> resArr(numArr.size(), 0);
std::vector<std::pair<int, std::size_t>> subRangeSortedArr = arrayOfSortedSubRange(4, numArr);
for(std::vector<std::pair<int, std::size_t>>::const_iterator it = subRangeSortedArr.cbegin(),
endIt = subRangeSortedArr.cend(); endIt != it;){
std::vector<std::pair<int, std::size_t>>::const_iterator rightNextSubRangeIt = it + std::min<std::ptrdiff_t>(
endIt - it, 4);
for(std::vector<std::pair<int, std::size_t>>::const_iterator eleIt = it; rightNextSubRangeIt != eleIt; ++eleIt){
std::size_t count = std::count_if(eleIt, rightNextSubRangeIt, [index = eleIt->second](
const std::pair<int, std::size_t>& element){ return index < element.second;});
if(endIt != rightNextSubRangeIt){
count += rightGreterElmentCountOfNumber(eleIt->first, rightNextSubRangeIt, endIt);
}
resArr[eleIt->second] = count;
}
it += std::min<std::ptrdiff_t>(endIt - it, 4);
}
return resArr;
}
int main(){
std::vector<std::size_t> res = rightGreaterElementCount({10, 12, 8, 17, 3, 24, 19});
cout<< "[10, 12, 8, 17, 3, 24, 19] => [";
std::copy(res.cbegin(), res.cbegin() + (res.size() - 1), std::ostream_iterator<std::size_t>(cout, ", "));
cout<< res.back()<< "]\n";
}
输出：
[10, 12, 8, 17, 3, 24, 19] => [4, 3, 3, 2, 2, 0, 0]