Java 中数组中的倒序计数

2024 年 9 月 26 日 | 阅读 19 分钟

给定一个包含整数的数组。任务是找出给定数组中的总逆序对数。总逆序对数是一个数字，它表明给定数组距离排序有多近或多远。对于排序后的数组，逆序对数为 0。如果数组按相反的顺序排序，则逆序对数对于该数组来说是最大的。请看以下示例。

示例 1

输入

int inArr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8}

输出 24

解释：给定的数组有以下逆序对

(7, 4), (7, 1), (7, 3), (7, 5), (7, 0), (7, 6), (7, 2), (4, 1), (4, 3), (4, 0), (4, 2), (9, 1), (9, 3), (9, 5), (9, 0), (9, 6), (9, 2), (9, 8), (1, 0), (3, 0), (3, 2), (5, 0), (5, 2), (6, 2)。因此，总逆序对数为 24。

示例 2

输入

int inArr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

输出 45

解释：所有元素均按严格递减顺序排列。因此，这次我们将得到最大的逆序对数。逆序对是

(9, 8), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0), (8, 7), (8, 6), (8, 5), (8, 4), (8, 3), (8, 2), (8, 1), (8, 0), (7, 6), (7, 5), (7, 4), (7, 3), (7, 2), (7, 1), (7, 0), (6, 5), (6, 4), (6, 3), (6, 2), (6, 1), (6, 0), (5, 4), (5, 3), (5, 2), (5, 1), (5, 0), (4, 3), (4, 2), (4, 1), (4, 0), (3, 2), (3, 1), (3, 0), (2, 1), (2, 0), (1, 0)，它们的计数为 (9 * (9 + 1)) / 2 = 45。

示例 3

输入

int inArr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

输出 0

解释：元素按递增顺序排列。因此，右侧没有更小的元素，使得逆序对数为 0。

示例 4

输入

int inArr[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

输出 0

解释：输入数组的所有元素都是常数，即相同的值。因此，输入数组的右侧不存在更小的元素。因此，逆序对数为 0。

方法：使用嵌套循环

在此方法中，我们将嵌套两个 for 循环。外层循环选择输入数组中的元素（将其视为当前元素）。内层循环从当前元素的下一个元素开始，一直遍历到末尾。在内层循环中，将内层循环变量指向的元素与当前元素进行比较。如果它更小，则将逆序对数增加 1；否则，不增加逆序对数。

文件名：CountInversion.java

// important import statements
import java.util.ArrayList;
import java.util.Arrays;

public class CountInversion 
{

public int computeInversionCount(ArrayList<Integer> inArr, int s) 
{   
int inversionCount = 0;

// outer loop picks the current element
for(int i = 0; i < s; i++)
{

for(int j = i + 1; j < s; j++)
{
if(inArr.get(i) > inArr.get(j))
{
// smaller element on the right side
// is found. Hence, increasing the 
// count by 1
inversionCount = inversionCount + 1;
}
}

}

return inversionCount;
}
    
// main method
public static void main(String argvs[])
{
// creating an object of the class CountInversion
CountInversion obj = new CountInversion();

// input 1
ArrayList<Integer> inArr = new ArrayList<Integer>
(
Arrays.asList(7, 4, 9, 1, 3, 5, 0, 6, 2, 8)
);

// computing the size of the 
// input array
int size = inArr.size();
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();
int ans = obj.computeInversionCount(inArr, size);

System.out.println("The total inversion count of the input array is: " + ans);

System.out.println();

// input 2
inArr = new ArrayList<Integer>
(
Arrays.asList(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeInversionCount(inArr, size);

System.out.println("The total inversion count of the input array is: " + ans);

System.out.println();

// input 3
inArr = new ArrayList<Integer>
(
Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeInversionCount(inArr, size);

System.out.println("The total inversion count of the input array is: " + ans);

System.out.println();


// input 4
inArr = new ArrayList<Integer>
(
Arrays.asList(4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
);

// computing the size of the 
// input array
size = inArr.size();

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(inArr.get(i) + " ");
}

System.out.println();

ans = obj.computeInversionCount(inArr, size);

System.out.println("The total inversion count of the input array is: " + ans);

}

}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The total inversion count of the input array is: 24

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The total inversion count of the input array is: 45

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The total inversion count of the input array is: 0

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The total inversion count of the input array is: 0

复杂度分析：由于程序使用了嵌套循环，因此程序的时间复杂度为 O(N2)。程序未使用任何额外空间。因此，程序空间复杂度为常数，即 O(1)。

方法：增强型归并排序

该方法是使用增强型归并排序。在此方法中，我们将首先将输入数组分成两个子数组，然后计算第一个和第二个子数组中的逆序对。之后，我们将计算合并子数组时的逆序对。总数就是答案。我们将递归地将输入数组分成子数组。找到解决方案的步骤如下。

步骤 1：在每个递归步骤中，将输入数组分成两个大致相等或相等的两半，直到达到基本情况。当给定的一半只有一个元素时，达到递归的基本情况。

步骤 2：创建一个 merge() 方法，该方法在合并输入数组的两个半部分时计算总逆序对数。创建两个索引 j 和 k，j 是第一个半部分的索引，k 是第二个半部分的专用索引。如果 inArr[j] 大于 inArr[k]，则存在 (mid - j) 个逆序对。这是因为右子数组和左子数组已排序，因此在左子数组中，所有剩余的元素 inArr[j + 1], inArr[j + 2] … inArr[mid]) 都将大于 inArr[k]。

步骤 3：另外，创建一个递归方法来将输入数组分成两半，并通过添加第一个半部分的逆序对数、第二个半部分的逆序对数以及合并两个半部分的逆序对数来计算答案。

步骤 4：显示总计数。

实施

观察上述步骤的实现。

文件名：CountInversion1.java

// important import statement
import java.util.Arrays;

public class CountInversion1  
{

// method for counting the inversions number
// during the process of merge
private static int mergeAndCount(int inArr[], int lt, int mid, int rt)
{

// The left subarray
int[] leftSubArr = Arrays.copyOfRange(inArr, lt, mid + 1);

// The right subarray
int[] rightSubArr = Arrays.copyOfRange(inArr, mid + 1, rt + 1);

int p = 0;
int q = 0;
int r = lt;
int swapCount = 0;

while (p < leftSubArr.length && q < rightSubArr.length) 
{
if (leftSubArr[p] <= rightSubArr[q])
{
inArr[r] = leftSubArr[p];
r = r + 1;
p = p + 1;
}
else 
{
// if the control reaches here,
// then it means we have got the inversions
// hence, we have to update the inversions count
inArr[r] = rightSubArr[q];
swapCount = swapCount + (mid + 1) - (lt + p);
r = r + 1;
q = q + 1;
}
}

// adding the remaining elements of the 
// left sub array
while (p < leftSubArr.length)
{
inArr[r] = leftSubArr[p];
r = r + 1;
p = p + 1;
}


// adding the remaining elements of the 
// right sub array
while (q < rightSubArr.length)
{
inArr[r] = rightSubArr[q];
r = r + 1;
q = q + 1;
}
return swapCount;
}

// Merge sort method for computing the inversions count
private static int mergeSortAndCount(int[] inArr, int lt, int rt)
{

// Keeping track of the inversion count at a
// specific node of the recursion tree
int cnt = 0;

if (lt < rt) 
{
int mid = (lt + rt) / 2;

// Total inversion count = count of left subarray count
// + count of right subarray + merge count

// count for the Left subarray
cnt = cnt + mergeSortAndCount(inArr, lt, mid);

// Count for the Right subarray 
cnt = cnt + mergeSortAndCount(inArr, mid + 1, rt);

// count after merge
cnt = cnt + mergeAndCount(inArr, lt, mid, rt);
}

return cnt;
}

// main method
public static void main(String[] argvs)
{
// input 1
int arr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8};

// computing the size of the input array
int n = arr.length;

// for storing the total inversions count
int ans;

// creating an object of the class CountInversion1
CountInversion1 obj = new CountInversion1();
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
// invoking the method mergeSortAndCount()
ans = obj.mergeSortAndCount(arr, 0, n - 1);

System.out.println();
System.out.println("The total inversions count is: " + ans);

System.out.println( );

// input 2
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

// computing the size of the input array
n = arr1.length;


System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
// invoking the method mergeSortAndCount()
ans = obj.mergeSortAndCount(arr1, 0, n - 1);

System.out.println();
System.out.println("The total inversions count is: " + ans);

System.out.println( );


// input 3
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// computing the size of the input array
n = arr2.length;


System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr2[i] + " ");
}
// invoking the method mergeSortAndCount()
ans = obj.mergeSortAndCount(arr2, 0, n - 1);

System.out.println();
System.out.println("The total inversions count is: " + ans);

System.out.println( );



// input 4
int arr3[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4};

// computing the size of the input array
n = arr3.length;

System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr3[i] + " ");
}
// invoking the method mergeSortAndCount()
ans = obj.mergeSortAndCount(arr3, 0, n - 1);

System.out.println();
System.out.println("The total inversions count is: " + ans);


}

}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The total inversions count is: 24

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The total inversions count is: 45

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The total inversions count is: 0

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The total inversions count is: 0

复杂度分析：归并排序需要 O(n x log(n)) 时间。因此，程序的时间复杂度为 O(n x log(n))。程序空间复杂度为 O(n)，因为使用辅助数组来存储左子数组和右子数组，其中 n 是输入数组中的元素总数。

方法：使用自平衡树

算法

步骤 1：创建一个 AVL 树。此外，在树的每个节点中添加一个属性，说明每个节点将包含其子树大小的信息。

步骤 2：从最后一个到第一个遍历输入数组。

步骤 3：对于每个元素，将其放入自平衡树（AVL 树）中。

步骤 4：大于当前元素的节点数可以通过检查右子树的大小（右子节点的数量）轻松计算得出。因此，可以肯定的是，当前节点右子树中的元素数量小于当前元素（因为我们是从后向前遍历输入数组）。此外，右子节点的值大于当前元素（AVL 树的属性）。因此，满足逆序条件。因此，将计数增加到当前插入节点的右子树大小。

步骤 5：显示计数。

文件名：CountInversion2.java

// important import statement
import java.util.*;

public class CountInversion2
{
int result = 0;
// An AVL tree node
static class AVLNode
{
int key;
AVLNode lft;
AVLNode rght;
int hght;

// size of the rooted tree 
int s;
};

// A method for finding the height of 
// the tree rooted with r
static int height(AVLNode r)
{
if (r == null)
{
return 0;
}
return r.hght;
}

// A method for size of the
// tree of rooted with r
static int size(AVLNode r)
{
if (r == null)
{
return 0;
}

return r.s;
}

// A Method for finding the maximum
// between p and q
static int findMax(int p, int q)
{
return (p > q) ? p : q;
}

// Helper Method for allocating the
// new node with the provided key. The method
// assigns a null value to the right and left pointers.
static AVLNode newNode(int key)
{
AVLNode nde = new AVLNode();
nde.key = key;
nde.lft = null;
nde.rght = null;

// At leaf, the new node is added at
// the beginning
nde.hght = 1;
nde.s = 1;
return(nde);
}


// A method for doing the right rotation of the 
// subtree rooted with r
static AVLNode rightRotate(AVLNode r)
{
AVLNode nde = r.lft;
AVLNode T2 = nde.rght;

// Perform rotation
nde.rght = r;
r.lft = T2;

// Update heights
r.hght = Math.max(height(r.lft), height(r.rght)) + 1;
nde.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;

// Updating the sizes
r.s = size(r.lft) + size(r.rght) + 1;
nde.s = size(nde.lft) + size(nde.rght) + 1;
// Updating the sizes
r.s = size(r.lft) + size(r.rght) + 1;
nde.s = size(nde.lft) + size(nde.rght) + 1;

// Returning the new root
return nde;
}

// A utility method for the left rotation of the 
// subtree rooted with r
public AVLNode leftRotate(AVLNode r)
{
AVLNode nde = r.rght;
AVLNode T2 = nde.lft;

// Performing the rotation
nde.lft = r;
r.rght = T2;

// Update heights
r.hght = Math.max(height(r.lft), height(r.rght)) + 1;
nde.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;

// Update sizes
r.s = size(r.lft) + size(r.rght) + 1;
nde.s = size(nde.lft) + size(nde.rght) + 1;

// Returning the new root
return nde;
}

// Getting the Balance factor of the node r
public int getBalance(AVLNode r)
{
if (r == null)
{
return 0;
}

return height(r.lft) - height(r.rght);
}

// The method inserts a new key into the AVL tree rooted with
// the node. Also, updating the count for fetching count
// of the lesser elements with the new key
public AVLNode insert(AVLNode nde, int key)
{
// Performing the rotation of the BST (normal)
if (nde == null)
{
return(newNode(key));
}

if (key < nde.key)
{
nde.lft = insert(nde.lft, key);
result = result + size(nde.rght) + 1;
}
else if(key > nde.key)
{
nde.rght = insert(nde.rght, key);
}

// the key value is the same as the nde value
// hence, that key value should not be inserted
else
{
return nde;
}


// Updating the size and the height of this ancestor node
nde.hght = Math.max(height(nde.lft), height(nde.rght)) + 1;
nde.s = size(nde.lft) + size(nde.rght) + 1;

// Getting the balance factor of the 
// ancestor node for checking whether the
// node has become unbalanced or not
int balanceFactor = getBalance(nde);

// If the node gets unbalanced,
// then we have the 4 cases to consider

// Handling the Left-Left Case
if (balanceFactor > 1 && key < nde.lft.key)
{
return rightRotate(nde);
}

// Handling the Right-Right Case
if (balanceFactor < -1 && key > nde.rght.key)
{
return leftRotate(nde);
}
// Handling the Left-Right Case
if (balanceFactor > 1 && key > nde.lft.key)
{
nde.lft = leftRotate(nde.lft);
return rightRotate(nde);
}

// handling the Right-Left Case
if (balanceFactor < -1 && key < nde.rght.key)
{
nde.rght = rightRotate(nde.rght);
return leftRotate(nde);
}

// Returning the node pointer that is unchanged
return nde;
}

// The following method is used to update the
// cntSmaller array for containing the count of
// the smaller elements on the right side.
public int countInv(int arr[], int size)
{
AVLNode rt = null;

// Beginning from the rightmost element,
// put all of the elements one by one in
// the AVL tree 
for(int i = 0; i < size; i++)
{
rt = insert(rt, arr[i]);
}

return result;
}


// main method
public static void main(String[] argvs)
{
// input 1
int arr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8};

// computing the size of the input array
int n = arr.length;

// for storing the total inversions count
int ans;

// creating an object of the class CountInversion2
CountInversion2 obj = new CountInversion2();
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
// invoking the method countInv()
ans = obj.countInv(arr, n);

System.out.println();
System.out.println("The total inversions count is: " + ans);

System.out.println( );

// input 2
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
// computing the size of the input array
n = arr1.length;
obj.result = 0;
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
// invoking the method countInv()
ans = obj.countInv(arr1, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
System.out.println( );
// input 3
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// computing the size of the input array
n = arr2.length;
obj.result = 0;
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr2[i] + " ");
}
// invoking the method countInv()
ans = obj.countInv(arr2, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
System.out.println( );
// input 4
int arr3[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
// computing the size of the input array
n = arr3.length;
obj.result = 0;
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr3[i] + " ");
}
// invoking the method countInv()
ans = obj.countInv(arr3, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
}
}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The total inversions count is: 24

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The total inversions count is: 45

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The total inversions count is: 0

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The total inversions count is: 0

复杂度分析：程序的时空复杂度与上一个程序相同。

方法：使用二叉索引树

使用二叉索引树也可以达到期望的结果。观察以下算法。

算法

使用二叉索引树也可以达到期望的结果。观察以下算法。

步骤 1：创建一个二叉索引树来查找小于某个数的元素的数量。还创建一个变量 res = 0。

步骤 2：从最后一个到第一个遍历输入数组。

步骤 3：对于每个索引，找出小于当前元素的元素总数，并将结果与之相加。

步骤 4：创建一个 retrieveSum() 方法来获取更少元素的数量。

步骤 5：通过执行更新操作将当前元素添加到数组 BIT[] 中，该操作将当前元素计数从 0 更新为 1，从而更新二叉索引树中的当前元素祖先。

文件名：CountInversion3.java

// important import statement
import java.util.*;
public class CountInversion3
{
// Returning the sum of arr[0 ... idx].
// This method makes the assumption that the
// array is already preprocessed, and the partial
// sums of the elements of the array are being stored
// in the BITTree[].
static int retrieveSum(int BITTree[], int idx)
{
// Initializing the result
int res = 0;
// Traversing the ancestors of the BITTree[idx]
while (idx > 0)
{
// Adding the current element of
// the BITree to the sum
res = res + BITTree[idx];
// Moving the index to the parent node
// in the getSretrieveSumum View
idx = idx - (idx & (-idx));
}
return res;
}
// Updating a node in the BIT
// at the provided index in the Binary Index Tree.
// The given value v is added to
// BITree[i] and all of its ancestors
// in tree.
static void updateBIT(int BITTree[], int n, int idx, int v)
{
// Traversing all of the ancestors
// and adding the value v
while (idx <= n)
{
// Adding the value v to the current
// node of the Binary Indexed Tree
BITTree[idx] = BITTree[idx] + v;

// Update index to that of
// parent in update View
idx = idx + (idx & (-idx));
}
}
// Converting the array into another array
// with the values ranging from 1 to n and
// also maintaining the relative order of the larger and
// the smaller elements still remain the same.
// For example, {7, -90, 100, 1}
// is converted to {3, 1, 4 ,2 }
static void convert(int inputArr[], int n)
{
// Creating a copy of the inputArr[] in temp
// and sort the temp array in
// increasing order
int temp[] = new int[n];
for (int k = 0; k < n; k++)
{
temp[k] = inputArr[k];
}
Arrays.sort(temp);
// Traversing all of the array elements
for (int k = 0; k < n; k++)
{
// lowerBound() is Returning a pointer
// to the first element, which is equal to or larger
// than inputArr[i]
inputArr[k] = lowerBound(temp, 0, n, inputArr[k]) + 1;
}
}
static int lowerBound(int[] arr, int l, int high, int ele)
{
while(l < high)
{
int mid = l + (high - l) / 2;
if(ele > arr[mid])
{
l = mid + 1;
}
else
{
high = mid;
}
}
return l;
}
// Returning the inversion count of the
// inputArr[0 ... n - 1]
static int getInvCount(int inputArr[], int n)
{
// Initializing the result
int inversionCount = 0;
// Converting inputArr[] to the array
// with the values from 1 to n and
// the relative order of the lesser
// and the larger elements remain the
// same. For example, {117, -900,
// 1, 300} is converted to
// {3, 1, 2, 4 }
convert(inputArr, n);

// Creating a Binary Indexed Tree with the size 
// same as the maxElement + 1 (The extra one is
// used so that the elements can be
// used directly as index)
int []BITArr = new int[n + 1];

for (int k = 1; k <= n; k++)
{
BITArr[k] = 0;
}
// Traversing all of the elements
// from the right.
for (int k = n - 1; k >= 0; k--)
{
// Getting the elements count
// that are smaller than the BITArr[k]
inversionCount = inversionCount + retrieveSum(BITArr, inputArr[k] - 1);
// Adding the current element to the BIT
updateBIT(BITArr, n, inputArr[k], 1);
}
return inversionCount;
}
// main method
public static void main(String[] argvs)
{
// input 1
int arr[] = {7, 4, 9, 1, 3, 5, 0, 6, 2, 8};

// computing the size of the input array
int n = arr.length;
// for storing the total inversions count
int ans;
// creating an object of the class CountInversion3
CountInversion3 obj = new CountInversion3();
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
// invoking the method getInvCount()
ans = obj.getInvCount(arr, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
System.out.println( );
// input 2
int arr1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

// computing the size of the input array
n = arr1.length;
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
// invoking the method getInvCount()
ans = obj.getInvCount(arr1, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
System.out.println( );
// input 3
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// computing the size of the input array
n = arr2.length;
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr2[i] + " ");
}
// invoking the method getInvCount()
ans = obj.getInvCount(arr2, n);
System.out.println();
System.out.println("The total inversions count is: " + ans);
System.out.println( );
// input 4
int arr3[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4};

// computing the size of the input array
n = arr3.length;

System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr3[i] + " ");
}
// invoking the method getInvCount()
ans = obj.getInvCount(arr3, n);

System.out.println();
System.out.println("The total inversions count is: " + ans);


}

}

输出

For the input array: 
7 4 9 1 3 5 0 6 2 8 
The total inversions count is: 24

For the input array: 
9 8 7 6 5 4 3 2 1 0 
The total inversions count is: 45

For the input array: 
0 1 2 3 4 5 6 7 8 9 
The total inversions count is: 0

For the input array: 
4 4 4 4 4 4 4 4 4 4 
The total inversions count is: 0

复杂度分析：程序的时空复杂度与上一个程序相同。

下一个主题Java 中计算右侧更小的元素

← 上一个下一个 →

Java 中数组中的倒序计数

方法：使用嵌套循环

方法：增强型归并排序

实施

方法：使用自平衡树

方法：使用二叉索引树

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中数组中的倒序计数

方法：使用嵌套循环

方法：增强型归并排序

实施

方法：使用自平衡树

方法：使用二叉索引树

相关帖子

判断给定字符串是否为回文的 Java 程序

How to Reverse a Number in Java

Reserve String without reverse() function

Java 在单链表开头插入新节点的程序

Java 中的灯泡链问题

在控制台上打印以下图案的 Java 程序 12

Java 在双向链表中搜索元素的程序

Java 从单链表开头删除节点的程序

查找循环链表中最大和最小值节点的 Java 程序

查找字符串中最长重复序列的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器