Java 以给定数组中大小为三的逆序对个数

逆序对计数是一种步骤计数方法，我们可以利用该方法计算特定数组所需要的排序步骤数。它还能计算数组的操作时间跨度。但是，如果我们想按照相反的顺序对数组进行排序，计数将会是数组中存在的最大数。

Array: { 5, 4, 3, 2, 1}  // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5}  // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5

逆序计数表示该特定数组与按升序排序之间的距离有多远。以下是两个描述此情况的特定过程及其解决方案-

寻找较小的元素- 为了从数组中找出较小的元素，我们需要从 n-1 迭代到 0 的索引。通过应用(a[i]-1)，我们可以在这里计算getSum()。该过程将持续到达a[i]-1。
寻找较大的数字- 要从索引中找出较大的数字，我们需要从 0 迭代到 n-1。对于每个元素，我们需要计算每个数字直到a[i]。将它从i中减去，然后我们将得到一个大于a[i]的数字。

数组中计数大小为三的逆序的算法：

在此算法中；我们学习如何在给定的数组中计数大小为三的逆序，具体的编程环境。

步骤 1 – 开始
步骤 2 – 声明一个数组和逆序计数（如arr[] -> 数组和invCount -> 逆序计数）
步骤 3 – 内部循环y=x+1到N
步骤 4 – 如果x索引处的元素大于y索引处的元素
步骤 5 – 然后，增加invCount++
步骤 6 – 打印该对
步骤 7 – 终止

数组中计数大小为三的逆序的语法：

如果存在一对 (A[i], A[j])，其中：A[i] > A[j] 且 i < j，则称其为逆序。

C++ 实现

int getInversions(int * A, int n) {
  int count = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (A[i] > a[j]) {
        ++count;
      }
    }
  }
  return count;
}

Java实现

public static int getInversions(int[] A, int n) {
  int count = 0;

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (A[i] > A[j]) {
        count += 1;
      }

    }
  }
  return count;
}

Python 实现

def getInversions(A, n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if A[i] > A[j]:
                count += 1

    return count;
}

在这里，我们提到了计算给定数组中大小为3的逆序对可能的语法。对于这种方法：时间复杂度为O(N^2)，其中N是数组的总大小；空间复杂度为O(1)，因为没有使用额外的空间。

需要遵循的方法

方法1 – 通过程序计算给定数组中大小为3的逆序对的方法
方法2 – 计算大小为3的逆序对的更好方法
方法3 – 使用二进制索引树计算大小为3的逆序对

方法1：通过程序计算给定数组中大小为3的逆序对

对于简单方法来计算大小为3的逆序对，我们需要为i、j和k的所有可能值运行循环。时间复杂度为O(n^3)，而O(1)表示辅助空间。

条件是：

a[i] > a[j] > a[k]，且i < j < k。

示例1

public class Inversion{
    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 after method: " +
                    inversion.getInvCount(arr, n));
    }
}

输出

Inversion count after method: 4

方法2：一种更好的方法来计算大小为3的逆序

在这种方法中，我们将数组的每个元素作为逆序的中间元素。这有助于减少复杂度。对于这种方法，时间复杂度为O(n^2)，辅助空间为O(1)。

示例2

public class Inversion {
    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++;
            int great = 0;
            for (int j=i-1; j>=0; j--)
                        if (arr[i] < arr[j])
                            great++;
            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 afret the operation : " +
                    inversion.getInvCount(arr, n));
    }
}

输出

Inversion count afret the operation : 4

方法3：使用二进制索引树计算大小为3的逆序数

在这种方法中，我们计算较大元素和较小元素的个数。然后将greater[]和smaller[]的乘积操作执行，并将其添加到最终结果中。这里的时间复杂度为O(n*log(n))，辅助空间为O(n)。

示例3

import java.io.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.*;
import java.util.Collections;

public class rudrabytp {
   static int N = 100005;
   static int BIT[][] = new int[4][N];
   static void updateBIT(int t, int i, int val, int n){
      while (i <= n) {
         BIT[t][i] = BIT[t][i] + val;
         i = i + (i & (-i));
      }
   }
   static int getSum(int t, int i){
      int res = 0;
      while (i > 0) {
         res = res + BIT[t][i];
         i = i - (i & (-i));
      }
      return res;
   }
   static void convert(int arr[], int n){
      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++) {
         arr[i] = Arrays.binarySearch(temp,arr[i]) + 1;
      }
   }
   public static int getInvCount(int arr[], int n){
      convert(arr, n);
      for (int i = n - 1; i >= 0; i--) {
         updateBIT(1, arr[i], 1, n);
         for (int l = 1; l < 3; l++) {
            updateBIT(l + 1, arr[i], getSum(l, arr[i] - 1), n);
         }
      }
      return getSum(3, n);
   }
   public static void main (String[] args){
      int arr[] = {8, 4, 2, 1};
      int n = arr.length;
      System.out.print("Inversion Count After The Operation : "+getInvCount(arr, n));
   }
}