数组的反转计数表示数组距离排序的距离（或距离）。如果数组已排序，则反转计数为0。如果数组按相反顺序排序，则反转计数为最大值。 如果a[i]>a[j]且i
null
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).
我们强烈建议您在继续解决方案之前单击此处并进行练习。
我们已经讨论了以下解决反转计数的方法：
我们建议您参考 二叉索引树（位） 在进一步阅读本文之前。 使用大小Θ位（maxElement）的解决方案：
- 方法： 遍历数组，为每个索引找到数组右侧较小元素的数量。这可以使用BIT来完成。将数组中所有索引的计数相加，然后打印总和。
- 比特的背景：
- BIT基本上支持大小为n的数组arr[]的两种操作：
- 在O（对数n）时间内，直到arr[i]的元素之和。
- 在O（logn）时间内更新数组元素。
- BIT使用数组实现，并以树的形式工作。请注意，有两种方法可以将BIT视为一棵树。
- 索引x的父级为“x–（x&-x）”的求和运算。
- 索引x的父级为“x+（x&-x）”的更新操作。
- BIT基本上支持大小为n的数组arr[]的两种操作：
- 算法：
- 实施
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 ?> |
Javascript
<script> // javascript 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) { var 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) { var invcount = 0; // Initialize result // Find maximum element in arr var 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) var BIT = Array.from({length: maxElement + 1}, (_, i) => 0); for (i = 1; i <= maxElement; i++) BIT[i] = 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 code var arr = [8, 4, 2, 1]; var n = arr.length; document.write( "Number of inversions are : " + getInvCount(arr,n)); // This code is contributed by Amit Katiyar </script> |
- 输出：
Number of inversions are : 6
- 复杂性分析：
- 时间复杂性：- update函数和getSum函数为O（log（maximumelement））运行。必须为数组中的每个元素运行getSum函数。所以总的时间复杂度是：O（nlog（maximumelement））。
- 辅助空间： O（maxElement），位所需的空间是最大元素大小的数组。
使用大小Θ（n）的位的更好解决方案：
- 方法： 遍历数组，为每个索引找到数组右侧较小元素的数量。这可以使用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 ofelements instead of a maximum element. Changingelement will not have any change in the answeras the greater elements remain greater and at thesame position.
- 算法：
- 创建一个位，以查找给定数字和变量位中较小元素的计数 结果=0 .
- 前面的解决方案不适用于包含负元素的数组。因此，将数组转换为包含元素相对编号的数组，即复制原始数组，然后对该数组的副本进行排序，并用排序数组中相同元素的索引替换原始数组中的元素。 例如，如果数组是{-3,2,0}，那么数组将转换为{1,3,2}
- 从头到尾遍历阵列。
- 对于每个索引，检查位中有多少小于当前元素的数字，并将其添加到结果中
- 实施：
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); } } // 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; } |
JAVA
// Java program to count inversions // using Binary Indexed Tree import java.util.*; 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) { // Initialize result int sum = 0 ; // 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); } } // 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 } static void convert( int arr[], int n) { // Create a copy of arrp[] in temp // and sort the temp array in // increasing order int []temp = new int [n]; for ( int i = 0 ; i < n; i++) temp[i] = arr[i]; Arrays.sort(temp); // 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, 0 , n, arr[i]) + 1 ; } } static int lower_bound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2 ; if (element > a[middle]) low = middle + 1 ; else high = middle; } return low; } // Returns inversion count // arr[0..n-1] static int getInvCount( int arr[], int n) { // Initialize result int invcount = 0 ; // 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 = new int [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 code public static void main(String[] args) { int arr[] = { 8 , 4 , 2 , 1 }; int n = arr.length; System.out.print( "Number of inversions are : " + getInvCount(arr, n)); } } // This code is contributed by Amit Katiyar |
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 |
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) { // Initialize result int sum = 0; // 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); } } // 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 } static void convert( int []arr, int n) { // Create a copy of arrp[] in temp // and sort the temp array in // increasing order int []temp = new int [n]; for ( int i = 0; i < n; i++) temp[i] = arr[i]; Array.Sort(temp); // 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,0, n, arr[i]) + 1; } } static int lower_bound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } // Returns inversion count // arr[0..n-1] static int getInvCount( int []arr, int n) { // Initialize result int invcount = 0; // 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 = new int [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 code public static void Main(String[] args) { int []arr = {8, 4, 2, 1}; int n = arr.Length; Console.Write( "Number of inversions are : " + getInvCount(arr, n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript 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) { // Initialize result let sum = 0; // 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); } } // 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 } function convert(arr, n) { // Create a copy of arrp[] in temp // and sort the temp array in // increasing order let temp = new Array(n); for (let i = 0; i < n; i++) temp[i] = arr[i]; temp.sort( function (a, b){ return a - b;}); // Traverse all array elements for (let 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,0, n, arr[i]) + 1; } } function lower_bound(a,low,high,element) { while (low < high) { let middle = low + Math.floor((high - low) / 2); if (element > a[middle]) low = middle + 1; else high = middle; } return low; } // Returns inversion count // arr[0..n-1] function getInvCount(arr,n) { // Initialize result let invcount = 0; // 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) let BIT = new Array(n + 1); for (let i = 1; i <= n; i++) BIT[i] = 0; // Traverse all elements // from right. for (let 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 code let arr=[8, 4, 2, 1]; let n = arr.length; document.write( "Number of inversions are : " + getInvCount(arr, n)); // This code is contributed by unknown2108 </script> |
- 输出：
Number of inversions are : 6
- 复杂性分析：
- 时间复杂性： update函数和getSum函数为O（log（n））运行。必须为数组中的每个元素运行getSum函数。所以总的时间复杂度是O（nlog（n））。
- 辅助空间： O（n）。 位所需的空间是一个大小为n的数组。
本文由Abhiraj Smit撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
