使用C++ STL中的Set计算右侧较小的元素 _date_date_set

编写一个函数以计算数组中每个元素右侧较小元素的数量。给定一个不同整数的未排序数组arr [], 请构造另一个数组countSmaller [], 以便countSmaller [i]包含数组中每个元素arr [i]右侧的较小元素的数量。
例子：

Input : arr[] ={12, 1, 2, 3, 0, 11, 4}Output :countSmaller[]={6, 1, 1, 1, 0, 1, 0} Input :arr[]={5, 4, 3, 2, 1}Output :countSmaller[]={4, 3, 2, 1, 0}

推荐：请尝试使用{IDE}首先, 在继续解决方案之前。在这篇文章中, 一个简单的实现https://www.lsbin.org/count-smaller-elements-on-right-side/讨论。
创建一个空的组inC ++ STL(请注意, C ++ STL中的Set是实现自平衡二进制搜索树的)。

将数组元素从i = len-1遍历到0, 并将每个元素插入集合中。
使用lower_bound函数查找低于A [i]的第一个元素。
使用距离函数找到上述找到的元素与集合开始之间的距离。
将距离存储在另一个数组中假设CountSmaller。
打印该数组。

// CPP program to find count of smaller // elements on right side using set in C++ // STL. #include < bits/stdc++.h> using namespace std; void countSmallerRight( int A[], int len) { set< int > s; int countSmaller[len]; for ( int i = len - 1; i > = 0; i--) { s.insert(A[i]); auto it = s.lower_bound(A[i]); countSmaller[i] = distance(s.begin(), it); }for ( int i = 0; i < len; i++) cout < < countSmaller[i] < < " " ; }// Driver code int main() { int A[] = {12, 1, 2, 3, 0, 11, 4}; int len = sizeof (A) / sizeof ( int ); countSmallerRight(A, len); return 0; }

输出如下：