如何计算数组中的逆序？S3（使用BIT）

2021年3月18日16:23:21 发表评论 897 次浏览

本文概述

数组的反转计数指示–数组要排序的距离(或距离)。如果已对数组进行排序, 则反转计数为0。如果以相反顺序对数组进行排序, 则反转计数为最大。

如果a [i]> a [j]并且i <j, 则两个元素a [i]和a [j]构成一个求逆。为简单起见, 我们可以假定所有元素都是唯一的。

例子：

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


Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3, 1), (3, 2).

强烈建议你在继续解决方案之前, 单击此处进行练习。

我们已经讨论了以下解决反转计数的方法：

  1. 天真的和修改的合并排序
  2. 使用AVL树

我们建议你参考二进制索引树(BIT)在进一步阅读这篇文章之前。

使用大小为Θ(maxElement)的BIT的解决方案：

方法：

遍历数组, 并为每个索引找到数组右侧较小元素的数量。这可以使用BIT完成。对数组中所有索引的计数求和, 然后打印总和。

BIT背景：

  1. 对于大小为n的数组arr [], BIT基本支持两种操作：
    1. 元素的总和, 直到O(Log n)时间的arr [i]。
    2. 在O(Log n)时间中更新数组元素。
  2. BIT是使用数组实现的, 并且以树的形式工作。请注意, 有两种将BIT视为树的方法。
    1. 索引x的父级为" x –(x＆-x)"的求和运算。
    2. 索引x的父级为" x +(x＆-x)"的更新操作。

算法：

  1. 创建一个BIT, 以查找给定数字和变量中BIT中较小元素的数量结果= 0.
  2. 从头到尾遍历数组。
  3. 对于每个索引, 请检查BIT中存在多少个小于当前元素的数字, 并将其添加到结果中
  4. 要获取较小元素的数量, BIT的getSum()用来。
  5. 在他的基本思想中, BIT表示为大小等于最大元素加一的数组。这样就可以将元素用作索引。
  6. 之后, 我们通过执行将当前元素的计数从0更新为1的更新操作, 将当前元素添加到BIT []中, 从而更新BIT中当前元素的祖先(请参见BIT中的update()有关详细信息)。

实现

C ++

// C++ program to count inversions using Binary Indexed Tree
#include<bits/stdc++.h>
using namespace std;
  
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum( int BITree[], int index)
{
     int sum = 0; // Initialize result
  
     // Traverse ancestors of BITree[index]
     while (index > 0)
     {
         // Add current element of BITree to sum
         sum += BITree[index];
  
         // Move index to parent node in getSum View
         index -= index & (-index);
     }
     return sum;
}
  
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree.  The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT( int BITree[], int n, int index, int val)
{
     // Traverse all ancestors and add 'val'
     while (index <= n)
     {
        // Add 'val' to current node of BI Tree
        BITree[index] += val;
  
        // Update index to that of parent in update View
        index += index & (-index);
     }
}
  
// Returns inversion count arr[0..n-1]
int getInvCount( int arr[], int n)
{
     int invcount = 0; // Initialize result
  
     // Find maximum element in arr[]
     int maxElement = 0;
     for ( int i=0; i<n; i++)
         if (maxElement < arr[i])
             maxElement = arr[i];
  
     // Create a BIT with size equal to maxElement+1 (Extra
     // one is used so that elements can be directly be
     // used as index)
     int BIT[maxElement+1];
     for ( int i=1; i<=maxElement; i++)
         BIT[i] = 0;
  
     // Traverse all elements from right.
     for ( int i=n-1; i>=0; i--)
     {
         // Get count of elements smaller than arr[i]
         invcount += getSum(BIT, arr[i]-1);
  
         // Add current element to BIT
         updateBIT(BIT, maxElement, arr[i], 1);
     }
  
     return invcount;
}
  
// Driver program
int main()
{
     int arr[] = {8, 4, 2, 1};
     int n = sizeof (arr)/ sizeof ( int );
     cout << "Number of inversions are : " << getInvCount(arr, n);
     return 0;
}

Java

// Java program to count inversions 
// using Binary Indexed Tree
  
class GFG
{
      
// Returns sum of arr[0..index]. 
// This function assumes that the 
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum( int [] BITree, int index)
{
     int sum = 0 ; // Initialize result
  
     // Traverse ancestors of BITree[index]
     while (index > 0 )
     {
         // Add current element of BITree to sum
         sum += BITree[index];
  
         // Move index to parent node in getSum View
         index -= index & (-index);
     }
     return sum;
}
  
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val' 
// is added to BITree[i] and all
// of its ancestors in tree.
static void updateBIT( int [] BITree, int n, int index, int val)
{
     // Traverse all ancestors and add 'val'
     while (index <= n)
     {
         // Add 'val' to current node of BI Tree
         BITree[index] += val;
  
         // Update index to that of parent in update View
         index += index & (-index);
     }
}
  
// Returns inversion count arr[0..n-1]
static int getInvCount( int [] arr, int n)
{
     int invcount = 0 ; // Initialize result
  
     // Find maximum element in arr[]
     int maxElement = 0 ;
     for ( int i = 0 ; i < n; i++)
         if (maxElement < arr[i])
             maxElement = arr[i];
  
     // Create a BIT with size equal to 
     // maxElement+1 (Extra one is used so 
     // that elements can be directly be
     // used as index)
     int [] BIT = new int [maxElement + 1 ];
     for ( int i = 1 ; i <= maxElement; i++)
         BIT[i] = 0 ;
  
     // Traverse all elements from right.
     for ( int i = n - 1 ; i >= 0 ; i--)
     {
         // Get count of elements smaller than arr[i]
         invcount += getSum(BIT, arr[i] - 1 );
  
         // Add current element to BIT
         updateBIT(BIT, maxElement, arr[i], 1 );
     }
  
     return invcount;
}
  
// Driver code
public static void main (String[] args)
{
     int []arr = { 8 , 4 , 2 , 1 };
     int n = arr.length;
     System.out.println( "Number of inversions are : " +
                                 getInvCount(arr, n));
}
}
  
// This code is contributed by mits

Python3

# Python3 program to count inversions using 
# Binary Indexed Tree 
  
# Returns sum of arr[0..index]. This function
# assumes that the array is preprocessed and 
# partial sums of array elements are stored 
# in BITree[]. 
def getSum( BITree, index):
     sum = 0 # Initialize result 
      
     # Traverse ancestors of BITree[index] 
     while (index > 0 ): 
  
         # Add current element of BITree to sum 
         sum + = BITree[index] 
  
         # Move index to parent node in getSum View 
         index - = index & ( - index) 
  
     return sum
  
# Updates a node in Binary Index Tree (BITree) 
# at given index in BITree. The given value
# 'val' is added to BITree[i] and all of its
# ancestors in tree. 
def updateBIT(BITree, n, index, val):
  
     # Traverse all ancestors and add 'val' 
     while (index < = n): 
  
         # Add 'val' to current node of BI Tree 
         BITree[index] + = val 
  
         # Update index to that of parent
         # in update View 
         index + = index & ( - index) 
  
# Returns count of inversions of size three 
def getInvCount(arr, n):
  
     invcount = 0 # Initialize result 
  
     # Find maximum element in arrays 
     maxElement = max (arr)
  
     # Create a BIT with size equal to 
     # maxElement+1 (Extra one is used 
     # so that elements can be directly 
     # be used as index)
     BIT = [ 0 ] * (maxElement + 1 ) 
     for i in range ( 1 , maxElement + 1 ): 
         BIT[i] = 0
     for i in range (n - 1 , - 1 , - 1 ):
  
         invcount + = getSum(BIT, arr[i] - 1 ) 
         updateBIT(BIT, maxElement, arr[i], 1 ) 
     return invcount 
      
# Driver code 
if __name__ = = "__main__" :
     arr = [ 8 , 4 , 2 , 1 ] 
     n = 4
     print ( "Inversion Count : " , getInvCount(arr, n))
      
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to count inversions 
// using Binary Indexed Tree
using System;
  
class GFG
{
      
// Returns sum of arr[0..index]. 
// This function assumes that the 
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum( int []BITree, int index)
{
     int sum = 0; // Initialize result
  
     // Traverse ancestors of BITree[index]
     while (index > 0)
     {
         // Add current element of BITree to sum
         sum += BITree[index];
  
         // Move index to parent node in getSum View
         index -= index & (-index);
     }
     return sum;
}
  
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val' 
// is added to BITree[i] and all
// of its ancestors in tree.
static void updateBIT( int []BITree, int n, int index, int val)
{
     // Traverse all ancestors and add 'val'
     while (index <= n)
     {
         // Add 'val' to current node of BI Tree
         BITree[index] += val;
  
         // Update index to that of parent in update View
         index += index & (-index);
     }
}
  
// Returns inversion count arr[0..n-1]
static int getInvCount( int []arr, int n)
{
     int invcount = 0; // Initialize result
  
     // Find maximum element in arr[]
     int maxElement = 0;
     for ( int i = 0; i < n; i++)
         if (maxElement < arr[i])
             maxElement = arr[i];
  
     // Create a BIT with size equal to 
     // maxElement+1 (Extra one is used so 
     // that elements can be directly be
     // used as index)
     int [] BIT = new int [maxElement + 1];
     for ( int i = 1; i <= maxElement; i++)
         BIT[i] = 0;
  
     // Traverse all elements from right.
     for ( int i = n - 1; i >= 0; i--)
     {
         // Get count of elements smaller than arr[i]
         invcount += getSum(BIT, arr[i] - 1);
  
         // Add current element to BIT
         updateBIT(BIT, maxElement, arr[i], 1);
     }
  
     return invcount;
}
  
// Driver code
static void Main()
{
     int []arr = {8, 4, 2, 1};
     int n = arr.Length;
     Console.WriteLine( "Number of inversions are : " +
                                 getInvCount(arr, n));
}
}
  
// This code is contributed by mits

的PHP

<?php
// PHP program to count inversions
// using Binary Indexed Tree
  
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial 
// sums of array elements are stored 
// in BITree[].
function getSum( $BITree , $index )
{
     $sum = 0; // Initialize result
  
     // Traverse ancestors of BITree[index]
     while ( $index > 0)
     {
         // Add current element of BITree to sum
         $sum += $BITree [ $index ];
  
         // Move index to parent node in getSum View
         $index -= $index & (- $index );
     }
     return $sum ;
}
  
// Updates a node in Binary Index 
// Tree (BITree) at given index
// in BITree. The given value 'val'
// is added to BITree[i] and
// all of its ancestors in tree.
function updateBIT(& $BITree , $n , $index , $val )
{
     // Traverse all ancestors and add 'val'
     while ( $index <= $n )
     {
         // Add 'val' to current node of BI Tree
         $BITree [ $index ] += $val ;
  
         // Update index to that of 
         // parent in update View
         $index += $index & (- $index );
     }
}
  
// Returns inversion count arr[0..n-1]
function getInvCount( $arr , $n )
{
     $invcount = 0; // Initialize result
  
     // Find maximum element in arr[]
     $maxElement = 0;
     for ( $i =0; $i < $n ; $i ++)
         if ( $maxElement < $arr [ $i ])
             $maxElement = $arr [ $i ];
  
     // Create a BIT with size equal
     // to maxElement+1 (Extra one is
     // used so that elements can be 
     // directly be used as index)
     $BIT = array_fill (0, $maxElement +1, 0);
  
     // Traverse all elements from right.
     for ( $i = $n -1; $i >=0; $i --)
     {
         // Get count of elements smaller than arr[i]
         $invcount += getSum( $BIT , $arr [ $i ]-1);
  
         // Add current element to BIT
         updateBIT( $BIT , $maxElement , $arr [ $i ], 1);
     }
  
     return $invcount ;
}
  
     // Driver program
     $arr = array (8, 4, 2, 1);
     $n = count ( $arr );
     print ( "Number of inversions are : " .getInvCount( $arr , $n ));
  
// This code is contributed by mits
?>

输出如下：

Number of inversions are : 6

复杂度分析：

  • 时间复杂度：-update函数和getSum函数运行O(log(maximumelement))。必须对数组中的每个元素运行getSum函数。因此, 总体时间复杂度为：O(nlog(maximumelement))。
  • 辅助空间：O(maxElement), BIT所需的空间是最大元素大小的数组。

使用大小为Θ(n)的BIT更好的解决方案：

方法：

遍历数组, 并为每个索引找到数组右侧较小元素的数量。这可以使用BIT完成。对数组中所有索引的计数求和, 然后打印总和。该方法保持不变, 但是前一种方法的问题是它不适用于负数, 因为索引不能为负。想法是将给定数组转换为值从1到n的数组, 较小和较大元素的相对顺序保持不变。

例子：-

arr[] = {7, -90, 100, 1}

It gets  converted to, arr[] = {3, 1, 4 , 2 }
as -90 < 1 < 7 < 100.

Explanation: Make a BIT array of a number of
elements instead of a maximum element. Changing
element will not have any change in the answer
as the greater elements remain greater and at the
same position.

算法：

  1. 创建一个BIT, 以查找给定数字和变量中BIT中较小元素的数量结果= 0.
  2. 先前的解决方案不适用于包含负元素的数组。因此, 将数组转换为包含元素相对编号的数组, 即制作原始数组的副本, 然后对数组的副本进行排序, 然后用已排序数组中相同元素的索引替换原始数组中的元素。
    例如, 如果数组为{-3, 2, 0}, 则该数组将转换为{1, 3, 2}
  3. 从头到尾遍历数组。
  4. 对于每个索引, 请检查BIT中存在多少个小于当前元素的数字, 并将其添加到结果中

实现

CPP

// C++ program to count inversions using Binary Indexed Tree
#include<bits/stdc++.h>
using namespace std;
  
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum( int BITree[], int index)
{
     int sum = 0; // Initialize result
  
     // Traverse ancestors of BITree[index]
     while (index > 0)
     {
         // Add current element of BITree to sum
         sum += BITree[index];
  
         // Move index to parent node in getSum View
         index -= index & (-index);
     }
     return sum;
}
  
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree.  The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT( int BITree[], int n, int index, int val)
{
     // Traverse all ancestors and add 'val'
     while (index <= n)
     {
        // Add 'val' to current node of BI Tree
        BITree[index] += val;
  
        // Update index to that of parent in update View
        index += index & (-index);
     }
}
  
// Converts an array to an array with values from 1 to n
// and relative order of smaller and greater elements remains
// same.  For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 , 2 }
void convert( int arr[], int n)
{
     // Create a copy of arrp[] in temp and sort the temp array
     // in increasing order
     int temp[n];
     for ( int i=0; i<n; i++)
         temp[i] = arr[i];
     sort(temp, temp+n);
  
     // Traverse all array elements
     for ( int i=0; i<n; i++)
     {
         // lower_bound() Returns pointer to the first element
         // greater than or equal to arr[i]
         arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
     }
}
  
// Returns inversion count arr[0..n-1]
int getInvCount( int arr[], int n)
{
     int invcount = 0; // Initialize result
  
      // Convert arr[] to an array with values from 1 to n and
      // relative order of smaller and greater elements remains
      // same.  For example, {7, -90, 100, 1} is converted to
     //  {3, 1, 4 , 2 }
     convert(arr, n);
  
     // Create a BIT with size equal to maxElement+1 (Extra
     // one is used so that elements can be directly be
     // used as index)
     int BIT[n+1];
     for ( int i=1; i<=n; i++)
         BIT[i] = 0;
  
     // Traverse all elements from right.
     for ( int i=n-1; i>=0; i--)
     {
         // Get count of elements smaller than arr[i]
         invcount += getSum(BIT, arr[i]-1);
  
         // Add current element to BIT
         updateBIT(BIT, n, arr[i], 1);
     }
  
     return invcount;
}
  
// Driver program
int main()
{
     int arr[] = {8, 4, 2, 1};
     int n = sizeof (arr)/ sizeof ( int );
     cout << "Number of inversions are : " << getInvCount(arr, n);
     return 0;
}

Python3

# Python3 program to count inversions using Binary Indexed Tree
from bisect import bisect_left as lower_bound
  
# Returns sum of arr[0..index]. This function assumes
# that the array is preprocessed and partial sums of
# array elements are stored in BITree.
def getSum(BITree, index):
  
     sum = 0 # Initialize result
  
     # Traverse ancestors of BITree[index]
     while (index > 0 ):
  
         # Add current element of BITree to sum
         sum + = BITree[index]
  
         # Move index to parent node in getSum View
         index - = index & ( - index)
  
     return sum
  
# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updateBIT(BITree, n, index, val):
  
     # Traverse all ancestors and add 'val'
     while (index < = n):
  
         # Add 'val' to current node of BI Tree
         BITree[index] + = val
  
     # Update index to that of parent in update View
     index + = index & ( - index)
  
# Converts an array to an array with values from 1 to n
# and relative order of smaller and greater elements remains
# same. For example, 7, -90, 100, 1 is converted to
# 3, 1, 4 , 2
def convert(arr, n):
  
     # Create a copy of arrp in temp and sort the temp array
     # in increasing order
     temp = [ 0 ] * (n)
     for i in range (n):
         temp[i] = arr[i]
     temp = sorted (temp)
  
     # Traverse all array elements
     for i in range (n):
  
         # lower_bound() Returns pointer to the first element
         # greater than or equal to arr[i]
         arr[i] = lower_bound(temp, arr[i]) + 1
  
# Returns inversion count arr[0..n-1]
def getInvCount(arr, n):
  
     invcount = 0 # Initialize result
  
     # Convert arr to an array with values from 1 to n and
     # relative order of smaller and greater elements remains
     # same. For example, 7, -90, 100, 1 is converted to
     # 3, 1, 4 , 2
     convert(arr, n)
  
     # Create a BIT with size equal to maxElement+1 (Extra
     # one is used so that elements can be directly be
     # used as index)
     BIT = [ 0 ] * (n + 1 )
  
     # Traverse all elements from right.
     for i in range (n - 1 , - 1 , - 1 ):
  
         # Get count of elements smaller than arr[i]
         invcount + = getSum(BIT, arr[i] - 1 )
  
         # Add current element to BIT
         updateBIT(BIT, n, arr[i], 1 )
  
     return invcount
  
# Driver program
if __name__ = = '__main__' :
  
     arr = [ 8 , 4 , 2 , 1 ]
     n = len (arr)
     print ( "Number of inversions are : " , getInvCount(arr, n))
  
# This code is contributed by mohit kumar 29

输出如下：

Number of inversions are : 6

复杂度分析：

  • 时间复杂度：update函数和getSum函数针对O(log(n))运行。必须对数组中的每个元素运行getSum函数。因此, 总体时间复杂度为O(nlog(n))。
  • 辅助空间：上)。
    BIT所需的空间是大小为n的数组。

本文由Abhiraj Smit提供。如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论

木子山

发表评论

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