Рубрики

Количество инверсий размера три в данном массиве

Дан массив arr [] размера n. Три элемента arr [i], arr [j] и arr [k] образуют инверсию размера 3, если a [i]> a [j]> a [k] и i <j <k. Найти общее количество инверсий размера 3.

Пример :

Input:  {8, 4, 2, 1}
Output: 4
The four inversions are (8,4,2), (8,4,1), (4,2,1) and (8,2,1).

Input:  {9, 6, 4, 5, 8}
Output:  2
The two inversions are {9, 6, 4} and {9, 6, 5}

Мы уже обсуждали счет инверсии второго размера с помощью сортировки слиянием , Self Balancing BST и BIT .

Простой подход: — Зациклить все возможные значения i, j и k и проверить условие a [i]> a [j]> a [k] и i <j <k.

C ++

// Простая C ++ O (n ^ 3) программа для подсчета инверсий размера 3
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество инверсий третьего размера

int getInvCount(int arr[],int n)

{

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

  

    for (int i=0; i<n-2; i++)

    {

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

        {

            if (arr[i]>arr[j])

            {

                for (int k=j+1; k<n; k++)

                {

                    if (arr[j]>arr[k])

                        invcount++;

                }

            }

        }

    }

    return invcount;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {8, 4, 2, 1};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Inversion Count : " << getInvCount(arr, n);

    return 0;

}

Джава

// Простая реализация Java для подсчета инверсии размера 3

class Inversion{

      

    // возвращает счетчик инверсии размера 3

    int getInvCount(int arr[], int n)

    {

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

          

        for(int i=0 ; i< n-2; i++)

        {

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

            {

                if(arr[i] > arr[j])

                {

                    for(int k=j+1; k<n; k++)

                    {

                        if(arr[j] > arr[k])

                            invcount++;

                    }

                }

            }

        }

        return invcount;

    }

  

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        Inversion inversion = new Inversion();

        int arr[] = new int[] {8, 4, 2, 1};

        int n = arr.length;

        System.out.print("Inversion count : "

                    inversion.getInvCount(arr, n));

    }

}
// Этот код предоставлен Mayank Jaiswal

питон

# Простая программа на Python O (n ^ 3)
# считать инверсии размера 3

  
# Возвращает количество инверсий
№ размера три

def getInvCount(arr):

    n = len(arr)

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

    for i in range(0,n-1):

        for j in range(i+1 , n):

                if arr[i] > arr[j]:

                    for k in range(j+1 , n):

                        if arr[j] > arr[k]:

                            invcount += 1

    return invcount

  
# Программа драйвера для проверки вышеуказанной функции

arr = [8 , 4, 2 , 1]

print "Inversion Count : %d" %(getInvCount(arr))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Простая реализация C # для
// считать инверсию размера 3

using System;

class GFG {

      
// возвращает счетчик инверсии размера 3

static int getInvCount(int []arr, int n)

    {

          

        // инициализировать результат

        int invcount = 0; 

          

          

        for(int i = 0 ; i < n - 2; i++)

        {

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

            {

                if(arr[i] > arr[j])

                {

                    for(int k = j + 1; k < n; k++)

                    {

                        if(arr[j] > arr[k])

                            invcount++;

                    }

                }

            }

        }

        return invcount;

    }

  

    // Код драйвера

    public static void Main()

    {

        int []arr = new int[] {8, 4, 2, 1};

        int n = arr.Length;

        Console.WriteLine("Inversion count : "

                           getInvCount(arr, n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// AO (n ^ 2) PHP программа для
// считать инверсии размера 3

  
// Возвращает количество
// инверсии размера 3

function getInvCount($arr, $n)

{

      

    // Инициализировать результат

    $invcount = 0; 

  

    for ($i = 1; $i < $n - 1; $i++)

    {

          

        // Подсчитать все более мелкие элементы

        // справа от arr [i]

        $small = 0;

        for($j = $i + 1; $j < $n; $j++)

            if ($arr[$i] > $arr[$j])

                $small++;

  

        // Подсчитать все большие элементы

        // слева от arr [i]

        $great = 0;

        for($j = $i - 1; $j >= 0; $j--)

            if ($arr[$i] < $arr[$j])

                $great++;

  

        // Обновить счетчик инверсий

        // добавляем все инверсии

        // которые имеют arr [i] как

        // середина трех элементов

        $invcount += $great * $small;

    }

  

    return $invcount;

}

  

    // Код драйвера

    $arr = array(8, 4, 2, 1);

    $n = sizeof($arr);

    echo "Inversion Count : "

        , getInvCount($arr, $n);

  
// Этот код предоставлен m_kit
?>


Выход:

Inversion Count : 4 

Временная сложность этого подхода: O (n ^ 3)

Лучший подход:
Мы можем уменьшить сложность, если рассмотрим каждый элемент arr [i] как средний элемент инверсии, найдем все числа, большие, чем [i], индекс которых меньше, чем i, найдем все числа, которые меньше, чем [i], и Индекс больше, чем я. Мы умножаем количество элементов больше, чем a [i], на количество элементов меньше, чем a [i], и добавляем его к результату.
Ниже приведена реализация идеи.

C ++

// AO (n ^ 2) C ++ программа для подсчета инверсий размера 3
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество инверсий размера 3

int getInvCount(int arr[], int n)

{

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

  

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

    {

        // Подсчитать все меньшие элементы справа от arr [i]

        int small = 0;

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

            if (arr[i] > arr[j])

                small++;

  

        // Считаем все большие элементы слева от arr [i]

        int great = 0;

        for (int j=i-1; j>=0; j--)

            if (arr[i] < arr[j])

                great++;

  

        // Обновить счетчик инверсий, добавив все инверсии

        // которые имеют arr [i] как середину трех элементов

        invcount += great*small;

    }

  

    return invcount;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {8, 4, 2, 1};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Inversion Count : " << getInvCount(arr, n);

    return 0;

}

Джава

// AO (n ^ 2) Java-программа для подсчета инверсий размера 3

  

class Inversion {

      

    // возвращает счетчик инверсии размера 3

    int getInvCount(int arr[], int n)

    {

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

          

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

        {

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

            int small=0;

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

                if (arr[i] > arr[j])

                    small++;

                      

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

            int great = 0;

            for (int j=i-1; j>=0; j--)

                        if (arr[i] < arr[j])

                            great++;

                      

            // обновляем счетчик инверсий, добавляя все инверсии

            // которые имеют arr [i] как середину трех элементов

            invcount += great*small;

        }

        return invcount;

    }

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        Inversion inversion = new Inversion();

        int arr[] = new int[] {8, 4, 2, 1};

        int n = arr.length;

        System.out.print("Inversion count : " +

                       inversion.getInvCount(arr, n));

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# AO (n ^ 2) Python3 программа для
# количество инверсий размера 3

  
# Возвращает количество инверсий
№ размера 3

def getInvCount(arr, n):

  

    # Инициализировать результат

    invcount = 0   

  

    for i in range(1,n-1):

      

        # Подсчитать все более мелкие элементы

        # справа от обр

        small = 0

        for j in range(i+1 ,n):

            if (arr[i] > arr[j]):

                small+=1

  

        # Подсчитать все большие элементы

        # слева от обр

        great = 0;

        for j in range(i-1,-1,-1):

            if (arr[i] < arr[j]):

                great+=1

  

        # Обновить счет инверсии

        # добавление всех инверсий, которые

        # иметь arr [i] в середине

        # три элемента

        invcount += great * small

      

    return invcount

  
# Программа драйвера для проверки вышеуказанной функции

arr = [8, 4, 2, 1]

n = len(arr)

print("Inversion Count :",getInvCount(arr, n))

  
# Этот код предоставлен Smitha Dinesh Semwal

C #

// AO (n ^ 2) Java-программа для подсчета инверсий
// размером 3

using System;

  

public class Inversion {

      

    // возвращает счетчик инверсии размера 3

    static int getInvCount(int []arr, int n)

    {

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

          

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

        {

              

            // считать все меньшие элементы на

            // право на обр [я]

            int small = 0;

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

                if (arr[i] > arr[j])

                    small++;

                      

            // посчитать все большие элементы на

            // слева от arr [i]

            int great = 0;

            for (int j = i-1; j >= 0; j--)

                        if (arr[i] < arr[j])

                            great++;

                      

            // обновляем счетчик инверсий

            // добавляем все инверсии, которые

            // иметь arr [i] в середине

            // три элемента

            invcount += great * small;

        }

          

        return invcount;

    }

      

    // программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

          

        int []arr = new int[] {8, 4, 2, 1};

        int n = arr.Length;

        Console.WriteLine("Inversion count : "

                       + getInvCount(arr, n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// AO (n ^ 2) PHP-программа для подсчета
// инверсии размера 3

  
// Возвращает количество
// инверсии размера 3

function getInvCount($arr, $n)

{

    // Инициализировать результат

    $invcount = 0; 

  

    for ($i = 1; $i < $n - 1; $i++)

    {

        // Подсчитать все более мелкие элементы

        // справа от arr [i]

        $small = 0;

        for ($j = $i + 1; $j < $n; $j++)

            if ($arr[$i] > $arr[$j])

                $small++;

  

        // Подсчитать все большие элементы

        // слева от arr [i]

        $great = 0;

        for ($j = $i - 1; $j >= 0; $j--)

            if ($arr[$i] < $arr[$j])

                $great++;

  

        // Обновить счетчик инверсий

        // добавляем все инверсии, которые

        // иметь arr [i] в середине

        // три элемента

        $invcount += $great * $small;

    }

  

    return $invcount;

}

  
// Код драйвера

$arr = array (8, 4, 2, 1);

$n = sizeof($arr);

echo "Inversion Count : "

      getInvCount($arr, $n);

      
// Этот код предоставлен m_kit
?>


Выход :

Inversion Count : 4 

Сложность времени этого подхода: O (n ^ 2)

Бинарный индексированный подход к дереву:
Подобно инверсиям размера 2, мы можем использовать двоичное индексированное дерево, чтобы найти инверсии размера 3. Настоятельно рекомендуется сначала обратиться к статье ниже.

Подсчет инверсий второго размера Использование BIT

Идея аналогична приведенному выше методу. Мы подсчитываем количество больших элементов и меньших элементов для всех элементов, а затем умножаем большее [] на меньшее [] и добавляем его к результату.

Решение :

  1. Чтобы узнать количество элементов меньшего размера для индекса, мы итерируем от n-1 до 0. Для каждого элемента a [i] мы вычисляем функцию getSum () для (a [i] -1), которая дает число элементов до а [I] -1.
  2. Чтобы узнать количество больших элементов для индекса, мы перебираем от 0 до n-1. Для каждого элемента a [i] мы вычисляем сумму чисел до a [i] (сумму, меньшую или равную a [i]) с помощью getSum () и вычитаем ее из i (поскольку i — общее количество элементов до этой точки ), чтобы мы могли получить число элементов больше, чем [i].
  3. Как и для инверсий размера 2 , здесь мы также конвертируем входной массив в массив со значениями от 1 до n, чтобы размер BIT оставался O (n), а функции getSum () и update () принимают O (Log). о) время Например, мы конвертируем arr [] = {7, -90, 100, 1} в arr [] = {3, 1, 4, 2}.

    Ниже приведена реализация вышеуказанной идеи.

    С

    // C ++ программа для подсчета инверсий третьего размера с использованием
    // Двоичное индексированное дерево
    #include<bits/stdc++.h>

    using namespace std;

      
    // Возвращает сумму arr [0..index]. Эта функция предполагает
    // что массив предварительно обработан и частичные суммы
    // элементы массива хранятся в BITree [].

    int getSum(int BITree[], int index)

    {

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

      

        // Пройдемся по предкам BITree [index]

        while (index > 0)

        {

            // Добавить текущий элемент BITree к сумме

            sum += BITree[index];

      

            // Переместить индекс на родительский узел в представлении getSum

            index -= index & (-index);

        }

        return sum;

    }

      
    // Обновляет узел в дереве двоичных индексов (BITree) по указанному индексу
    // в BITree. Заданное значение 'val' добавляется в BITree [i] и
    // все его предки в дереве.

    void updateBIT(int BITree[], int n, int index, int val)

    {

        // Обходим всех предков и добавляем 'val'

        while (index <= n)

        {

           // Добавить 'val' к текущему узлу дерева BI

           BITree[index] += val;

      

           // Обновить индекс до родительского в обновлении View

           index += index & (-index);

        }

    }

      
    // Преобразует массив в массив со значениями от 1 до n
    // и сохраняется относительный порядок меньших и больших элементов
    // одна и та же. Например, {7, -90, 100, 1} преобразуется в
    // {3, 1, 4, 2}

    void convert(int arr[], int n)

    {

        // Создаем копию arrp [] в temp и сортируем временный массив

        // в порядке возрастания

        int temp[n];

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

            temp[i] = arr[i];

        sort(temp, temp+n);

      

        // Обход всех элементов массива

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

        {

            // lower_bound () Возвращает указатель на первый элемент

            // больше или равно arr [i]

            arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;

        }

    }

      
    // Возвращает количество инверсий третьего размера

    int getInvCount(int arr[], int n)

    {

        // Преобразовать arr [] в массив со значениями от 1 до n и

        // сохраняется относительный порядок меньших и больших элементов

        // одна и та же. Например, {7, -90, 100, 1} преобразуется в

        // {3, 1, 4, 2}

        convert(arr, n);

      

        // Создать и инициализировать меньшие и большие массивы

        int greater1[n], smaller1[n];

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

            greater1[i] = smaller1[i] = 0;

      

        // Создаем и инициализируем массив для хранения Binary

        // Индексированное дерево

        int BIT[n+1];

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

            BIT[i]=0;

      

        for(int i=n-1; i>=0; i--)

        {

            smaller1[i] = getSum(BIT, arr[i]-1);

            updateBIT(BIT, n, arr[i], 1);

        }

      

        // Сбросить БИТ

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

            BIT[i] = 0;

      

        // Считаем большие элементы

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

        {

            greater1[i] = i - getSum(BIT,arr[i]);

            updateBIT(BIT, n, arr[i], 1);

        }

      

        // Подсчитать количество инверсий, используя меньшие [] и

        // больше [].

        int invcount = 0;

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

            invcount += smaller1[i]*greater1[i];

      

        return invcount;

    }

      
    // Программа драйвера для проверки вышеуказанной функции

    int main()

    {

        int arr[] = {8, 4, 2, 1};

        int n = sizeof(arr)/sizeof(arr[0]);

        cout << "Inversion Count : " << getInvCount(arr, n);

        return 0;

    }

    Джава

    // Java-программа для подсчета инверсий третьего размера
    // Двоичное индексированное дерево

    import java.util.Arrays;

      

    class BinaryTree {

      

       // Возвращает сумму arr [0..index]. Эта функция предполагает

       // что массив предварительно обработан и частичные суммы

       // элементы массива хранятся в BITree [].

        int getSum(int BITree[], int index) {

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

      

            // Пройдемся по предкам BITree [index]

            while (index > 0) {

      

                // Добавить текущий элемент BITree к сумме

                sum += BITree[index];

      

                // Переместить индекс на родительский узел в представлении getSum

                index -= index & (-index);

            }

            return sum;

        }

      

        // Обновляет узел в дереве двоичных индексов (BITree) в данный момент

        // индекс в BITree. Данное значение 'val' добавляется к

        // BITree [i] и все его предки в дереве.

        void updateBIT(int BITree[], int n, int index, int val) {

          

            // Обходим всех предков и добавляем 'val'

            while (index <= n) {

          

                // Добавить 'val' к текущему узлу дерева BI

                BITree[index] += val;

      

                // Обновить индекс до родительского в обновлении View

                index += index & (-index);

            }

        }

      

        // Преобразует массив в массив со значениями от 1 до n

        // и сохраняется относительный порядок меньших и больших элементов

        // одна и та же. Например, {7, -90, 100, 1} преобразуется в

        // {3, 1, 4, 2}

        void convert(int arr[], int n) {

              

            // Создаем копию arrp [] в temp и сортируем временный массив

            // в порядке возрастания

            int temp[]= new int[n];

            for (int i = 0; i < n; i++) {

                temp[i] = arr[i];

            }

            Arrays.sort(temp);

      

            // Обход всех элементов массива

            for (int i = 0; i < n; i++) {

             

                // lower_bound () Возвращает указатель на первый элемент

                // больше или равно arr [i]

                arr[i] = Arrays.binarySearch(temp, arr[i])  + 1;

            }

        }

      

        // Возвращает количество инверсий третьего размера

        int getInvCount(int arr[], int n) {

             

            // Преобразовать arr [] в массив со значениями от 1 до n и

            // сохраняется относительный порядок меньших и больших элементов

            // одна и та же. Например, {7, -90, 100, 1} преобразуется в

            // {3, 1, 4, 2}

            convert(arr, n);

      

            // Создать и инициализировать меньшие и большие массивы

            int greater1[]= new int[n];

            int smaller1[]= new int[n];

            for (int i = 0; i < n; i++) {

                greater1[i] = smaller1[i] = 0;

            }

      

            // Создаем и инициализируем массив для хранения Binary

            // Индексированное дерево

            int BIT[]= new int[n+1];

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

                BIT[i] = 0;

            }

      

            for (int i = n - 1; i >= 0; i--) {

                smaller1[i] = getSum(BIT, arr[i] - 1);

                updateBIT(BIT, n, arr[i], 1);

            }

      

            // Сбросить БИТ

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

                BIT[i] = 0;

            }

      

            // Считаем большие элементы

            for (int i = 0; i < n; i++) {

                greater1[i] = i - getSum(BIT, arr[i]);

                updateBIT(BIT, n, arr[i], 1);

            }

      

            // Подсчитать количество инверсий, используя меньшие [] и

            // больше [].

            int invcount = 0;

            for (int i = 0; i < n; i++) {

                invcount += smaller1[i] * greater1[i];

            }

      

            return invcount;

        }

      

        // Программа драйвера для проверки вышеуказанной функции

        public static void main(String args[]) {

            BinaryTree tree = new BinaryTree();

            int[] arr = new int[]{8, 4, 2, 1};

            int n = arr.length;

            System.out.print( "Inversion Count : "

                               tree.getInvCount(arr, n));

        }

    }

      
    // Этот код предоставлен Mayank Jaiswal

    C #

    // C # программа для подсчета инверсий
    // размера три с использованием двоичного индексированного дерева

    using System; 

      

    class GFG 

    {

      
    // Возвращает сумму arr [0..index].
    // Эта функция предполагает, что
    // массив предварительно обработан и
    // частичные суммы элементов массива
    // хранятся в BITree [].

    int getSum(int[] BITree, int index) 

    {

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

      

        // Траверс предков

        // BITree [index]

        while (index > 0) 

        {

      

            // Добавить текущий элемент

            // BITree к сумме

            sum += BITree[index];

      

            // Переместить индекс в родительский узел

            // в getSum View

            index -= index & (-index);

        }

        return sum;

    }

      
    // Обновляет узел в двоичном индексе
    // Дерево (BITree) по заданному индексу
    // в BITree. Данное значение
    // val добавляется в BITree [i] и
    // все его предки в дереве.

    void updateBIT(int[] BITree, int n, 

                   int index, int val) 

    {

      

        // Пройдите через всех предков

        // и добавляем 'val'

        while (index <= n) 

        {

      

            // Добавить 'val' к текущему

            // узел дерева BI

            BITree[index] += val;

      

            // Обновить индекс до

            // родитель в обновлении View

            index += index & (-index);

        }

    }

      
    // Преобразует массив в массив
    // со значениями от 1 до n и
    // относительный порядок меньшего и
    // большие элементы остаются прежними.
    // Например, {7, -90, 100, 1}
    // конвертируется в {3, 1, 4, 2}

    void convert(int[] arr, int n) 

    {

          

        // Создать копию arrp [] в

        // темп и сортировка временного массива

        // в порядке возрастания

        int[] temp = new int[n];

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

        {

            temp[i] = arr[i];

        }

        Array.Sort(temp);

      

        // Обход всех элементов массива

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

        {

          

            // lower_bound () Возвращает указатель

            // к первому элементу больше

            // чем или равно arr [i]

            arr[i] = Array.BinarySearch(temp, 

                                        arr[i]) + 1;

        }

    }

      
    // Возвращает количество инверсий
    // размера три

    int getInvCount(int[] arr, int n) 

    {

          

        // Преобразовать arr [] в массив с

        // значения от 1 до n и относительные

        // порядок меньше и больше

        // элементы остаются такими же. За

        // пример, {7, -90, 100, 1}

        // преобразовано в {3, 1, 4, 2}

        convert(arr, n);

      

        // Создать и инициализировать

        // меньшие и большие массивы

        int[] greater1 = new int[n];

        int[] smaller1 = new int[n];

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

        {

            greater1[i] = smaller1[i] = 0;

        }

      

        // Создать и инициализировать

        // массив для хранения двоичного индексированного дерева

        int[] BIT = new int[n + 1];

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

        {

            BIT[i] = 0;

        }

      

        for (int i = n - 1; i >= 0; i--) 

        {

            smaller1[i] = getSum(BIT, 

                                 arr[i] - 1);

            updateBIT(BIT, n, arr[i], 1);

        }

      

        // Сбросить БИТ

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

        {

            BIT[i] = 0;

        }

      

        // Считаем большие элементы

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

        {

            greater1[i] = i - getSum(BIT,

                                     arr[i]);

            updateBIT(BIT, n, arr[i], 1);

        }

      

        // Подсчитать количество инверсий, используя

        // меньше [] и больше [].

        int invcount = 0;

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

        {

            invcount += smaller1[i] * 

                        greater1[i];

        }

      

        return invcount;

    }

      
    // Код драйвера

    public static void Main()

    {

        GFG tree = new GFG();

        int[] arr = new int[]{8, 4, 2, 1};

        int n = arr.Length;

        Console.Write( "Inversion Count : "

                        tree.getInvCount(arr, n));

    }
    }

      
    // Этот код добавлен
    // ChitraNayal

    python3

    # Python3 программа для подсчета инверсий
    # размер три с использованием двоичного индексированного дерева

      
    # Возвращает сумму arr [0..index]. Эта функция
    # предполагает, что массив предварительно обработан и
    # сохранены частичные суммы элементов массива
    # в BITree [].

    def getSum(BITree, index):

        sum = 0 # Инициализировать результат

          

        # Траверс предков BITree [index]

        while (index > 0): 

      

            # Добавить текущий элемент

            # BITree к сумме

            sum += BITree[index] 

      

            # Переместить индекс на родительский узел

            # в getSum View

            index -= index & (-index) 

      

        return sum

      
    # Обновляет узел в дереве двоичных индексов
    # (BITree) по указанному индексу в BITree.
    # Данное значение 'val' добавлено в BITree [i]
    # и все его предки в дереве.

    def updateBIT( BITree, n, index, val):

      

        # Пройдите через всех предков и добавьте 'val'

        while (index <= n): 

      

            # Добавить 'val' в текущий узел дерева BI

            BITree[index] += val 

      

            # Обновить индекс до родительского

            # в обновлении Просмотр

            index += index & (-index) 

      
    # Преобразует массив в массив со значениями
    # от 1 до n и относительный порядок меньше
    # и большие элементы остаются неизменными. Например,
    # 7, -90, 100, 1 преобразуется в 3, 1, 4, 2

    def convert(arr, n) :

      

        # Создайте копию arrp [] в temp и

        # сортировка временного массива в порядке возрастания

        temp = [0] *

        for i in range(n):

            temp[i] = arr[i] 

        temp = sorted(temp)

        j = 1

          

        # Обходить все элементы массива

        for i in temp: 

      

            # lower_bound () Возвращает пи

            # первый элемент больше чем

            # или равно arr [i]

            arr[arr.index(i)] = j

            j += 1

      
    # Возвращает количество инверсий третьего размера

    def getInvCount( arr, n):

      

        # Конвертировать arr [] в массив со значениями

        # от 1 до n и относительный порядок меньше

        # и большие элементы остаются неизменными. Например,

        # 7, -90, 100, 1 преобразуется в 3, 1, 4, 2

        convert(arr, n) 

      

        # Создайте и инициализируйте меньше и

        # большие массивы

        greater1 = [0] * n

        smaller1 = [0] *

        for i in range(n):

            greater1[i], smaller1[i] = 0, 0

      

        # Создать и инициализировать массив

        # store Двоичное индексированное дерево

        BIT = [0] * (n + 1

        for i in range(1, n + 1): 

            BIT[i] = 0

        for i in range(n - 1, -1, -1):

      

            smaller1[i] = getSum(BIT, arr[i] - 1

            updateBIT(BIT, n, arr[i], 1

      

        # Сбросить БИТ

        for i in range(1, n + 1): 

            BIT[i] = 0

      

        # Считать большие элементы

        for i in range(n): 

      

            greater1[i] = i - getSum(BIT, arr[i]) 

            updateBIT(BIT, n, arr[i], 1

      

        # Вычислить количество инверсий с помощью меньшего []

        # и выше [].

        invcount = 0

        for i in range(n): 

            invcount += smaller1[i] * greater1[i] 

      

        return invcount 

          
    # Код драйвера

    if __name__ =="__main__":

        arr= [8, 4, 2, 1

        n = 4

        print("Inversion Count : "

               getInvCount(arr, n))

          
    # Этот код предоставлен
    # Шубхам Сингх (SHUBHAMSINGH10)

    Выход:

    Inversion Count : 4 

    Сложность времени: O (n log n)
    Вспомогательное пространство: O (n)

    Мы также можем использовать самобалансирующееся дерево бинарного поиска для подсчета больших элементов слева и меньших справа. Временная сложность этого метода также будет O (n Log n), но метод, основанный на BIT, прост в реализации.

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

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

    Количество инверсий размера три в данном массиве

    0.00 (0%) 0 votes