本文概述

• 强烈建议你在继续解决方案之前, 单击此处进行练习。
• C ++
• Java
• Python3
• C#
• 的PHP
• CPP
• Python3

数组的反转计数指示–数组要排序的距离(或距离)。如果已对数组进行排序, 则反转计数为0。如果以相反顺序对数组进行排序, 则反转计数为最大。
如果a [i]> a [j]并且i < j, 则两个元素a [i]和a [j]构成一个求逆。为简单起见, 我们可以假定所有元素都是唯一的。
例子：

Input: arr[] = {8, 4, 2, 1}Output: 6Explanation: Given array has six inversions:(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).Input: arr[] = {3, 1, 2}Output: 2Explanation: 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 Treeclass 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 getsconverted to, arr[] = {3, 1, 4 , 2 }as -90 < 1 < 7 < 100.Explanation: Make a BIT array of a number ofelements instead of a maximum element. Changingelement will not have any change in the answeras the greater elements remain greater and at thesame position.

【如何计算数组中的逆序（S3（使用BIT））】算法：

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提供。如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论

推荐阅读

• 

  互联网销售数据分析
• 

  redis解决高并发问题,如商品秒杀 redis高并发架构与底层原理
• 

  tcl洗衣机快洗要多久 tcl洗衣机快速洗衣多久
• 

  销售是做什么的 销售具体是做什么的
• 

  缅甸红酸枝是红木吗
• 

  射击游戏最帅角色排行榜，射击游戏高手
• 

  adb push build.prop system 重启后无法进入系统解决方法
• 

  莆田本土“19+17”:含15名小学生
• 

  道声|道声 再见
• 

  哪些食物含有花青素 为什么鸡蛋和紫薯一起就变绿
• 

  DOTA2暗影萨满怎么玩 DOTA2小y技能介绍
• 

  sap现金管理与预算控制，erp现金管理
• 

  pdf阅读器的文字怎么粘贴复制
• 

  豁牙巴是什么意思 豁牙巴应该是什么意思
• 

  新冠疫苗|海口新增19个60岁及以上人群新冠疫苗接种点 老年人接种点达27个
• 

  健康码灰色几天能变绿
• 

  支付宝账户管理在哪
• 

  mongodb 集合内文档之间关联 mongodb 合并数据
• 

  儿童肾病综合症治疗方法首选 儿童肾病综合症治疗方法
• 

  管钳价格 「管钳什么牌子的最好」

• Linux虚拟化（如何使用cgroup进行资源限制（））
• Python Tkinter中的消息小部件如何使用（）
• jQuery如何使用first方法（示例）
• JavaScript布尔如何使用valueOf()方法（）
• Python MySQL如何使用更新查询（）
• 8085程序如何将二进制数转换为灰色（）
• 如何使用JavaScript单击时如何选择HTML文本输入中的所有文本（）
• Android中调用百度地图
• Android.mk解析