Рубрики

Подсчет инверсий с использованием Set в C ++ STL

Число инверсий для массива указывает — насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсий является максимальным.

    Two elements a[i] and a[j] form an inversion if 
     a[i] > a[j] and i < j. For simplicity, we may 
     assume that all elements are unique.

     Example:
     Input:  arr[] = {8, 4, 2, 1}
     Output: 6
     Given array has six inversions (8,4), (4,2),
     (8,2), (8,1), (4,1), (2,1).     

Мы уже обсуждали ниже подходы.
1) Наивный подход и сортировка слиянием.
2) AVL Основанный на дереве подход.

В этом посте обсуждается простая реализация подхода 2 с использованием Set в C ++ STL .

1) Create an empty Set in C++ STL (Note that a Set in C++ STL is 
   implemented using Self-Balancing Binary Search Tree). And insert
   first element of array into the set.

2) Initialize inversion count as 0.

3) Iterate from 1 to n-1 and do following for every element in arr[i]
     a) Insert arr[i] into the set.
     b) Find the first element greater than arr[i] in set
        using upper_bound() defined Set STL.
     c) Find distance of above found element from last element in set
        and add this distance to inversion count.

4) Return inversion count.

// Подход на основе STL для подсчета инверсий
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество инверсий в arr [0..n-1]

int getInvCount(int arr[],int n)

{

    // Создать пустой набор и вставить в него первый элемент

    multiset<int> set1;

    set1.insert(arr[0]);

  

    int invcount = 0; // Инициализировать результат

  

    multiset<int>::iterator itset1; // Итератор для множества

  

    // Обход всех элементов, начиная со второго

    for (int i=1; i<n; i++)

    {

        // Вставляем arr [i] в набор (обратите внимание, что набор поддерживает

        // отсортированный порядок)

        set1.insert(arr[i]);

  

        // Установить итератор на первый больший элемент, чем arr [i]

        // в наборе (обратите внимание, что набор хранит arr [0], .., arr [i-1]

        itset1 = set1.upper_bound(arr[i]);

  

        // Получить расстояние первого большего элемента от конца

        // и это расстояние - количество больших элементов

        // в левой части 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 : "

         << getInvCount(arr,n);

    return 0;

}

Выход:

Number of inversions count are : 6

Обратите внимание, что сложность времени в наихудшем случае описанной выше реализации составляет O (n 2 ), так как функция расстояния в STL принимает O (n) худший случай времени, но эта реализация намного проще, чем другие реализации, и в среднем займет намного меньше времени, чем метод Naive. ,

Эта статья предоставлена Абхираджем Смитом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчет инверсий с использованием Set в C ++ STL

0.00 (0%) 0 votes