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

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

编写一个函数以计算数组中每个元素右侧较小元素的数量。给定一个不同整数的未排序数组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是实现自平衡二进制搜索树的)。

  1. 将数组元素从i = len-1遍历到0, 并将每个元素插入集合中。
  2. 使用lower_bound函数查找低于A [i]的第一个元素。
  3. 使用距离函数找到上述找到的元素与集合开始之间的距离。
  4. 将距离存储在另一个数组中假设CountSmaller。
  5. 打印该数组。
// 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;
}

输出如下:

6 1 1 1 0 1 0

注意, 由于距离函数的最坏情况下的时间复杂度为O(n), 因此上述实现采用最坏情况下的时间复杂度O(n ^ 2), 但是以上实现非常简单, 并且比一般情况下的朴素算法更好。

以上方法适用于唯一元素, 但对于重复元素只需替换组与多集.


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: