Java 程序用于计算给定数组中大小为 3 的反转次数

javaobject oriented programmingprogramming更新于 2024/3/27 22:36:17

反转计数是一种步数计数方法,通过该方法我们可以计算特定数组所采取的排序步骤数。它还能够计算数组的操作时间跨度。但是,如果我们想以反向方式对数组进行排序,则计数将是该数组中存在的最大数字。

数组:{ 5, 4, 3, 2, 1} // 用于反向方式
对:{5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
输出:10
数组:{1, 2, 3, 4, 5} // 用于递增方式
对:无对
输出:0
数组:{1,5,2,8,3,4}
对:{5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
输出:5

反转计数表示该特定数组距离按递增顺序排序还有多远。下面是两个特定的过程来描述这种情况,并附上解决方案 -

  • 要找到较小的元素 - 要从数组中找出较小的元素,我们需要迭代索引从 n-1 到 0。通过应用 (a[i]-1),我们可以在此处计算 getSum()。该过程将运行,直到它达到 a[i]-1。

  • 要找到更大的数字 - 要从索引中找到更大的数字,我们需要执行迭代 0 到 n-1。对于每个元素,我们需要对每个数字进行计算,直到 a[i]。从 i 中减去它。然后我们将得到一个大于 a[i] 的数字。

用于计算数组中大小为三的反转的算法:-

在此算法中;我们学习如何在特定的编程环境中计算给定数组中大小为 3 的反转。

  • 步骤 1 - 开始

  • 步骤 2 - 声明一个数组和反转计数(作为 arr[] --> 数组和 invCount --> 反转计数)

  • 步骤 3 - 内部循环 y=x+1 到 N

  • 步骤 4 - 如果 x 处的元素大于 y 索引处的元素

  • 步骤 5 - 然后,增加 invCount++

  • 步骤 6 - 打印对

  • 步骤 7 - 终止

用于计算数组中大小为 3 的反转的语法:-

一对如果 A[i] > A[j] 且 i < j,则称 (A[i], A[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 的反转次数,以计算大小为 3 的反转次数

  • 方法 2 - 计算大小为 3 的反转次数的更好方法

  • 方法 3 - 使用二叉索引树计算大小为 3 的反转次数

使用程序计算给定数组中大小为 3 的反转次数,以计算大小为 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.getInvCount(arr, n));
	}
}

输出

方法后的反转计数:4

一种更好的方法来计算大小为 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.getInvCount(arr, n));
	}
}

输出

操作后的反转计数:4

使用二叉索引树计算大小为 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("操作后的反转计数:"+getInvCount(arr, n));
   }
}

输出

操作后的反转计数:4

结论

在本文中,我们今天学习了如何计算给定数组中大小为 3 的反转。希望通过本文和使用特定语言的所提及的代码,您对这个主题有一个广泛的了解。


相关文章


有用资源