Đếm nghịch đảo bằng cách sử dụng Đặt trong C ++ STL

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tính số nghịch đảo bằng cách sử dụng bộ trong C ++ STL.

Số lượng đảo ngược là thước đo mức độ gần của mảng được sắp xếp hoàn toàn. Nếu mảng đã được sắp xếp, số lượng đảo ngược sẽ là 0.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
//returning inversion count
int get_Icount(int arr[],int n){
   multiset<int> set1;
   set1.insert(arr[0]);
   int invcount = 0; //initializing result
   multiset<int>::iterator itset1;
   for (int i=1; i<n; i++){
      set1.insert(arr[i]);
      itset1 = set1.upper_bound(arr[i]);
      invcount += distance(itset1, set1.end());
   }
   return invcount;
}
int main()
{
   int arr[] = {8, 4, 2, 1};
   int n = sizeof(arr)/sizeof(int);
   cout << "Number of inversions count are : "<< get_Icount(arr,n);
   return 0;
}

Đầu ra

Number of inversions count are : 6