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

2021年3月17日14:20:23 发表评论 849 次浏览

编写一个函数以计算数组中每个元素右侧较小元素的数量。给定一个不同整数的未排序数组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;
}

输出如下：