逆序数

2024年8月28日 | 阅读 27 分钟

什么是反转计数？

反转计数概念用于数组，并且可以使用数组数据结构来实现。在反转计数中，我们将指定如何对数组进行排序。我们需要找到一对元素，其中第一个元素总是大于第二个元素。

如果数组已经排序，则总反转计数为 0。
但是，如果数组按降序排序，则总反转计数最大，因为我们将能够找到数组中存在的所有最大元素对。
为了识别正确的对，我们将遍历数组，然后找到位于 i 索引的元素并将其与 **(i + 1) 索引** 进行比较；如果发现它大于下一个索引，则我们将形成一对，并将反转计数加一。
通过这种方式，我们将从第 0 个索引开始遍历整个数组，直到第 (n-1) 个索引，并在找到符合上述条件的正确对时增加反转计数值。

让我们通过一个例子来理解它 -

我们给出了一个数组。

示例 1

给定

A = { 10 , 1 , 2 , 4 , 13 , 9 , 5 }

输出

在上面的示例中，您需要通过比较每个值与其他值来找出从第 0 个索引到最后一个索引的总反转次数。

并且可能出现的反转次数如下： **{ ( 10 , 1 ) , ( 10 , 2 ) , ( 10 , 4 ) , ( 10 , 9 ) , ( 10 , 5 ) , ( 13 , 9 ) , ( 13 , 5 ) , ( 9 , 5 ) }**

反转总计数为：8

示例 2

给定

A = { 1 , 5 , 2 , 4 , 13 , 19 , 15 }

输出

在上面的示例中，您需要通过比较每个值与其他值来找出从第 0 个索引到最后一个索引的总反转次数。

并且可能出现的反转次数如下： **{ ( 5 , 2 ) , ( 5 , 4 ) , ( 19 , 15 ) }**

反转总计数为：3

示例 3

给定

A = { 7 , 5 , 12 , 4 , 1 , 9 , 15 , 3 , 8 }

输出

在上面的示例中，找出从第 0 个索引到最后一个索引的总反转次数，方法是比较每个值与其他值。

并且可能出现的反转次数如下： **{ ( 7 , 5 ) , ( 7 , 4 ) , ( 7 , 1 ) , ( 7 , 3 ) , ( 5 , 4 ) , ( 5 , 1 ) , ( 5 , 3 ) , ( 12 , 4 ) , ( 12 , 1 ) , ( 12 , 9 ) , ( 12 , 3 ) , ( 12 , 8 ) , ( 4 , 1 ) , ( 4 , 3 ) , ( 15 , 3 ) , ( 15 , 8 ) }**

反转总计数为：16

示例 4

给定

A = { 17 , 15 , 12 , 11 , 10 , 9 , 8 , 3 , 1 }

输出

在上面的示例中，找出从第 0 个索引到最后一个索引的总反转次数，方法是比较每个值与其他值。

并且可能出现的反转次数如下： **{ ( 17 , 15 ) , ( 17 , 12 ) , ( 17 , 11 ) , ( 17 , 10 ) , ( 17 , 9 ) , ( 17 , 8 ) , ( 17 , 3 ) , ( 17 , 1 ) , ( 15 , 12 ) , ( 15 , 11 ) , ( 15 , 10 ) , ( 15 , 9 ) , ( 15 , 8 ) , ( 15 , 3 ) , ( 15 , 1 ) , ( 12 , 11 ) , ( 12 , 10 ) , ( 12 , 9 ) , ( 12 , 8 ) , ( 12 , 3 ) , ( 12 , 1 ) , ( 11 , 10 ) , ( 11 , 9 ) , ( 11 , 8 ) , ( 11 , 3 ) , ( 11 , 1 ) , ( 10 , 9 ) , ( 10 , 8 ) , ( 10 , 3 ) , ( 10 , 1 ) , ( 9 , 8 ) , ( 9 , 3 ) , ( 9 , 1 ) , ( 8 , 3 ) , ( 8 , 1 ) , ( 3 , 1 ) }**

反转总计数为：36

在这里，如果我们观察，我们有一个按降序排序的数组，并且我们获得了最大的反转计数，因为数组中的每个元素都大于其后面的元素。

示例 5

给定

A = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }

输出

在上面的示例中，您需要通过比较每个值与其他值来找出从第 0 个索引到最后一个索引的总反转次数。

并且可能出现的反转次数如下： **{ }**

反转总计数为：0

在这里，我们观察到我们有一个按升序排序的数组，并且我们得到了最小的反转计数，即 0，因为每个元素都小于其后面的元素。

示例 6

给定

A = {17 , 5 , 12 , 4 , 1 , 9 , 3 , 8}

输出

在上面的示例中，找出从第 0 个索引到最后一个索引的总反转次数，方法是比较每个值与其他值。

并且可能出现的反转次数如下： **{ ( 17 , 5 ) , ( 17 , 12 ) , ( 17 , 4 ) , ( 17 , 1 ) , ( 17 , 9 ) , ( 17 , 3 ) , ( 17 , 8 ) , ( 5 , 4 ) , ( 5 , 1 ) , ( 5 , 3 ) , ( 12 , 4 ) , ( 12 , 1 ) , ( 12 , 9 ) , ( 12 , 3 ) , ( 12 , 8 ) , ( 4 , 1 ) , ( 4 , 3 ) , ( 9 , 3 ) , ( 9 , 8 ) }**

反转总计数为：19

现在，让我们继续，因为我们已经看到在这个问题中我们将做什么。使用各种编程语言只会显示可能出现的反转次数，只有反转计数的值。

用于解决上述反转计数问题的常用方法

简单方法
使用归并排序

让我们逐一详细讨论这些方法，并分析每种方法的时空复杂度，以便比较两种方法中的更好者。

使用简单方法解决反转计数问题

在此方法中，我们将使用简单方法；首先，我们将遍历整个数组，从起始索引到最后一个索引，然后将右侧元素与所有其他元素进行比较。如果当前元素大于另一个元素，则我们将增加反转计数。此过程将继续，直到我们检查给定数组的最后一个元素。最后，我们将打印出所有可能出现的反转计数。为此，我们将使用嵌套循环技术。

让我们详细讨论解决此问题的算法步骤并计算总反转计数

解决反转计数问题的实现算法 -

步骤 1 - 从用户那里获取一个包含 'n' 个元素的数组；元素指的是主函数中的非负整数。用户输入的数组可以按任何顺序，不一定按升序或降序输入。

步骤 2 - 创建一个名为 **inversion** 的新函数，该函数将一个 **数组** 和数组中的元素数量作为参数从主函数接收。它将原始数组传递给它，并将该函数生成的 i 结果存储在主函数中的某个名为 **count** 的变量中。此函数将返回主数组中找到的总反转计数。

步骤 3 - 在 inversion 函数中，将一个名为 arr 的数组和名为 'n' 的数组大小作为参数传递，然后声明一个名为 'ic' 的变量并将其初始化为 0，它将表示数组中存在的总反转次数。

步骤 4 - 为了计算反转计数，我们需要运行两个循环；一个循环嵌套在另一个循环内部，第一个循环从索引 0 运行到 n-1 索引，然后另一个循环从索引 j = i + 1 运行到 n - 1，以便将 i 索引处的值与该索引之后的所有其他值进行比较。

步骤 5 - 在嵌套循环的主体中，我们分配了一个条件语句，在其中我们将比较 i 索引处的值与 j 索引处的值。如果 i 索引处的值大于 j 索引处的值，那么我们将 'ic' 的计数加 1，否则我们将检查下一个 j 索引。

步骤 6 - 以上述方式，我们将遍历整个数组，检查直到最后一个索引的所有值，最后返回 ic 作为结果。

步骤 7 - 从主函数，我们将打印出总反转计数的值。

使用上述方法在 C 编程语言中实现反转计数问题 -

/* C program to find the total number of inversion counts possible using the method discussed above*/
#include <stdio.h>
/* The program will print the count of total number of inversions possible from an random array */
int  Inversion ( int arr[] , int n )
{
	int ic = 0 , i , j ;
	for ( i = 0 ; i < n ; i++ )                  // This loop will point the target index //
	{
		for ( j = i + 1 ; j < n ; j++ )                   // This loop will compare the target  //
// index with all the other values arriving after it. //
		{
			if ( arr [ i ] > arr [ j ] )
			{
				ic = ic + 1 ;
			}
		}
	}
	return ic ;
}
int main()
{
	int i , array[ 100 ] , n , count ;
	printf ( " Enter the number of elements present in the array : " ) ;
	scanf ( "%d" , &n ) ;
	printf( " Enter array: " ) ;
	for ( i = 0 ;  i < n ; i++ )
	{
		scanf ( "%d" , &array[ i ] ) ;
	}
	count = Inversion ( array , n  ) ;
	printf ( " Printing the total number of inversions possible from the above array: %d " , count ) ;
	
	return 0 ;
}

上述程序的输出为

Enter number of elements present in the array: 8
 Enter array: 10
8
1
9
4
12
20
13
  Printing the total number of inversions possible from the above array: 8

使用上述方法在 C++ 编程语言中实现反转计数问题 -

/* C++ program to find the total number of inversion counts possible using the method discussed above*/
#include <iostream>
using namespace std ;
/* The program will print the count of the total number of inversions possible from a random array */
int  Inversion ( int arr[], int n )
{
	int ic = 0 , i , j ;
	for ( i = 0 ; i < n ; i++ )                  // This loop will point the target index //
	{
		for ( j = i + 1 ; j < n ; j++ )                   // This loop will compare the target //
// index with all the other values arriving after it. //
		{
			if ( arr [ i ] > arr [ j ] )
			{
				ic = ic + 1 ;
			}
		}
	}
	return ic ;
}
int main()
{
	int i , array[ 100 ] , n , count ;
	cout << " Enter the number of elements present in the array : " ;
	cin >> n ;
	cout << " Enter array: " << endl ;
	for ( i = 0 ;  i < n ; i++ )
	{
		cin >> array [ i ] ;
	}
	count = Inversion ( array , n  ) ;
	cout <<  " Printing the total number of inversions possible from the above array: " << count << endl ;
	
	return 0 ;
}

上述程序的输出为

7
6
1
4
12
2
3
0
6
  Printing the total number of inversions possible from the above array: 30

使用上述方法在 Java 编程语言中实现反转计数问题 -

/* Java program to find the total number of inversion counts possible using the method discussed above*/
/* The program will print the count of the total number of inversions possible from a random array */

import java.util.Scanner ;  
class Main {
	
	static int Inversion(int arr[], int n )
	{
		int ic = 0 , i , j ;
	for ( i = 0 ; i < n ; i++ )                  // This loop will point the target index //
	{
		for ( j = i + 1 ; j < n ; j++ )                   // This loop will compare the target //
                                              // index with all the other values arriving after it. //
		{
			if ( arr [ i ] > arr [ j ] )
			{
				ic = ic + 1 ;
			}
		}
	}
	return ic ;
}

	public static void main(String[] args)
	{
		int n ;
 Scanner sc = new Scanner ( System.in ) ;
 System.out.println ( " Enter the total number of elements :  " ) ;
 n = sc.nextInt() ;
 int [] A = new int[ 100 ] ;
 System.out.println ( " Enter elements of the array :  " ) ;
 for ( int i = 0 ; i < n ; i++ )
 {
	 A[ i ] = sc.nextInt() ;
 }
 
 int count = Inversion( A , n ) ;
 System.out.println( " The total number of inversion counts possible is: " +count );
	}
}

上述程序的输出为

Enter number of elements present in the array: 9
 Enter array: 
19
7
16
1
4
1
2
3
6
  Printing the total number of inversions possible from the above array: 23

使用上述方法在 Python 编程语言中实现反转计数问题 -

# Python program to find the total number of inversion counts possible using the method discussed above

# The program will print the count of the total number of inversions possible from a random array 

def Inversion(arr, n):

  ic = 0
  for i in range(n):                   # This loop will point the target index 
    for j in range(i + 1, n):                  # This loop will compare the target 
                                              # index with all the other values arriving after it.

      if (arr[i] > arr[j]):
        ic = ic + 1

  return ic

A = [10, 2, 6, 14, 5, 11, 9, 0, 1, 8]
n = len(A)
print("The total number of inversions possible are: ", Inversion(A, n))

上述程序的输出为

The total number of inversions possible are: 27

使用上述方法在 C# 编程语言中实现反转计数问题 -

/* C#  program to find the total number of inversion counts possible using the method discussed above*/
/* The program will print the count of the total number of inversions possible from a random array */
using System;
using System.Collections.Generic;

class Main {

	static int[] arr = new int[] { 11, 2, 16, 14, 5, 7, 8, 9, 1 };

	static int Inversion(int n)
	{
		int ic = 0;

		for (int i = 0; i < n - 1; i++)       // This loop will point the target index //

			for (int j = i + 1; j < n; j++)       // This loop will compare the target //
                                                      // index with all the other values arriving after it. //

				if (arr[i] > arr[j])
					ic = ic + 1;

		return ic;
	}
	public static void Main()
	{
		Console.WriteLine("The total number of "
						+ "inversions possible are:  "
						+ Inversion(arr.Length));
	}
}

上述程序的输出为

The total number of inversions possible are: 22

正如我们已经看到了使用简单方法实现反转计数问题，现在我们将分析上述问题以及上述实现方法的空间和时间复杂度。

上述简单方法解决反转计数问题的时复杂度 -

为了分析时间复杂度，我们将检查代码的每一行并找出每一行的复杂度。在这里，我们需要两个循环；一个循环嵌套在另一个循环内部。执行第一个循环需要 n 个元素 n 次，同样对于嵌套循环，我们需要 n 次，因为它是嵌套的，所以两个循环的时间复杂度将被相乘，最后我们将得到时间复杂度为 n² 加上一些常数。

T ( n ) = O ( n ).O ( n ) + C

T ( n ) = O ( n² ) + C

因此，时间复杂度将为 O ( n² )，因为我们进行了渐近的粗略估计，即我们需要 ' n² ' 的时间来解决 ' n ' 个元素的问题。这里 C 表示某个常数值。

上述简单方法解决反转计数问题的空间复杂度 -

为了找出空间复杂度，我们需要观察程序并分析存储所有变量所需的空间；当我们注意到程序时，我们将观察到不需要额外的空间来存储元素。

S ( n ) = O ( 1 )

使用归并排序方法解决反转计数问题

在此方法中，我们将使用归并排序的概念；在归并排序中，我们首先将数组分解为多个子数组，直到达到基本情况，然后我们将应用归并概念通过比较右子数组与左子数组的值来合并数组。

但是在这方面，我们将做一些轻微的改变，在这里数组的分区将与我们在归并排序中进行的相同，我们将深入数组直到得到单个大小的子数组。之后我们将合并它们。在合并时，我们将计算左侧存在的反转总数，同样在右侧计算，并维护计数并按原始顺序合并，最后可以轻松计算可能出现的所有反转总数。通过这种方法，与上述方法相比，我们可以减小时间复杂度。

让我们详细讨论解决此问题的算法步骤并计算总反转计数

解决反转计数问题的实现算法 -

步骤 1 - 从用户那里获取一个包含 'n' 个元素的数组；元素指的是主函数中的非负整数。用户输入的数组可以按任何顺序，不一定按升序或降序输入。

步骤 2 - 在这里，我们必须创建两个函数，分别名为 **merge_sort** 函数和 **merge** 函数。

步骤 3 - 从主函数，我们将调用 MS 函数，将原始数组和数组大小作为参数传递给它。

步骤 4 - MS 函数只接受一个数组和数组大小作为参数。但在此函数内部，我们将创建一个大小与传入参数大小相同的动态数组；然后，我们将调用一个名为 **merge_sort** 的函数，并将参数传递给它，即原始数组、我们最近创建的临时数组、数组大小和初始索引，即 0。

步骤 5 - 在 merge_sort 函数中，我们将有一个数组，数组大小 'n'，左侧和右侧作为参数，表示为 - merge_sort ( arr, n, l, r )。在此函数中，我们将首先检查左部分是否小于右部分，如果为真，我们将通过取左值和右值的平均值来找到中间值。

步骤 6 - 我们将先内部调用 merge_sort 从 l 到 mid，然后第二次从 mid + 1 到 r。在此函数中，我们将返回反转计数的值；因此，我们将反转计数的值存储在 ic 中，并首先将其初始化为 0。

步骤 7 - 在两次调用 merge_sort 函数后，我们将调用 merge 函数；merge 函数将数组、数组大小、左、中和右部分作为参数，它将返回反转计数的值。

步骤 8 - 在 merge 函数中，我们将合并两个数组并比较一个数组的每个值与另一个数组，如果我们发现左子数组的值大于右子数组，我们将增加反转计数。

步骤 9 - 最初，在 merge 函数中，我们将指针 i 从索引 left 开始，指针 j 从 mid 开始，然后我们将 i 和 j 在 while 条件下绑定，并从 i 为 left 到 mid - 1，j 为 mid 到 right 运行循环，然后我们将比较 arr [ i ] 的值与 arr [ j ] 的值。如果我们发现 arr [ i ] > arr [ j ]，那么我们将增加反转计数的值，该值最初初始化为 0，此外，在此，我们还将添加一个额外的因子，即 mid - 1，因为左右子数组已经排序，所以我们将得到 mid - 1 的额外反转。

步骤 10 - 在 merge_sort 函数中返回反转计数的值，并通过 merge_sort 函数计算并返回主函数中的反转计数聚合值。

步骤 11 - 最后，从主函数，我们将打印出给定数组可能出现的总反转计数的值。

使用上述方法在 C 编程语言中实现反转计数问题 -

/* C program to find the total number of inversion counts possible using the method discussed above*/
#include <stdio.h>
/* The program will print the count of total number of inversions possible from an random array */
#include <stdlib.h>

int merge_sort(int arr[], int temp[], int l, int r);
int merge(int arr[], int temp[], int l, int mid, int r);


int MS(int arr[], int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	return merge_sort(arr, temp, 0, size - 1);
}

int merge_sort(int arr[], int temp[], int l, int r)
{
	int mid, ic = 0;
	if (r > l) {
		

		mid = (r + l) / 2;

		

		ic = ic + merge_sort(arr, temp, l, mid);
		ic = ic + merge_sort(arr, temp, mid + 1, r);

		/*Merge the two parts*/
		ic = ic + merge(arr, temp, l, mid + 1, r);
	}
	return ic;
}

/* This funt merges two sorted
arrays and returns inversion
count in the arrays.*/
int merge(int arr[], int temp[], int l, int mid,	int r)
{
	int i, j, k;
	int ic = 0;

	i = l; /* i is index for left subarray*/
	j = mid; /* j is index for right subarray*/
	k = l; /* k is index for resultant merged subarray*/
	while ((i <= mid - 1) && (j <= r)) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];

			/*this is tricky -- see above
			* explanation/diagram for merge()*/
			ic = ic + (mid - i);
		}
	}

	/* Copy the remaining elements of left subarray
(if there are any) to temp*/
	while (i <= mid - 1)
		temp[k++] = arr[i++];

	/* Copy the remaining elements of right subarray
(if there are any) to temp*/
	while (j <= r)
		temp[k++] = arr[j++];

	/*Copy back the merged elements to original array*/
	for (i = l; i <= r; i++)
		arr[i] = temp[i];

	return ic;
}


int main()
{
	int i , array[ 100 ] , n , count ;
	printf ( " Enter the number of elements present in the array : " ) ;
	scanf ( "%d" , &n ) ;
	printf( " Enter array: " ) ;
	for ( i = 0 ;  i < n ; i++ )
	{
		scanf ( "%d" , &array[ i ] ) ;
	}
	count = MS ( array , n ) ;
	printf ( " Printing the total number of inversions possible from the above array: %d " , count ) ;
	
	return 0 ;
}

上述程序的输出为

Enter number of elements present in the array: 9
 Enter array: 
19
7
16
1
4
1
2
3
6
  Printing the total number of inversions possible from the above array: 23

使用上述方法在 C++ 编程语言中实现反转计数问题 -

/* C++ program to find the total number of inversion counts possible using the method discussed above*/
#include <iostream>
/* The program will print the count of total number of inversions possible from an random array */
#include <stdlib.h>
using namespace std ;

int merge_sort(int arr[], int temp[], int l, int r);
int merge(int arr[], int temp[], int l, int mid, int r);


int MS(int arr[], int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	return merge_sort(arr, temp, 0, size - 1);
}

int merge_sort(int arr[], int temp[], int l, int r)
{
	int mid, ic = 0;
	if (r > l) {
		

		mid = (r + l) / 2;

		/* Inversion count will be the sum of inversions in
		right-part, left-part and number of inversions in
		merging */
		ic = ic + merge_sort(arr, temp, l, mid);
		ic = ic + merge_sort(arr, temp, mid + 1, r);

		/*Merge the two parts*/
		ic = ic + merge(arr, temp, l, mid + 1, r);
	}
	return ic;
}

/* This funt merges two sorted
arrays and returns inversion
count in the arrays.*/
int merge(int arr[], int temp[], int l, int mid,	int r)
{
	int i, j, k;
	int ic = 0;

	i = l;             /* i is the index for left subarray*/
	j = mid;             /* j is the index for right subarray*/
	k = l; /* k is index for resultant merged subarray*/
	while ((i <= mid - 1) && (j <= r)) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];

			/*this is tricky -- see above
			* explanation/diagram for merge()*/
			ic = ic + (mid - i);
		}
	}

	/* Copy the remaining elements of left subarray
(if there are any) to temp*/
	while (i <= mid - 1)
		temp[k++] = arr[i++];

	/* Copy the remaining elements of right subarray
(if there are any) to temp*/
	while (j <= r)
		temp[k++] = arr[j++];

	
	for (i = l; i <= r; i++)
		arr[i] = temp[i];

	return ic;
}

int main()
{
	int i , array[ 100 ] , n , count ;
	cout << " Enter the number of elements present in the array : " << endl ;
	cin >> n;
	cout << " Enter array: " << endl ;
	for ( i = 0 ;  i < n ; i++ )
	{
		cin >> array[ i ] ;
	}
	count = MS ( array , n ) ;
	cout << " Printing the total number of inversions possible from the above array: " << count << endl ;
	
	return 0 ;
}

上述程序的输出为

Enter number of elements present in the array: 8
 Enter array: 10
8
1
9
4
12
20
13
  Printing the total number of inversions possible from the above array: 8

使用上述方法在 JAVA 编程语言中实现反转计数问题 -

/* JAVA  program to find the total number of inversion counts possible using the method discussed above*/
/* The program will print the count of the total number of inversions possible from a random array */
import java.util.*;
public classic {

	// Function to count the number of inversions
	// during the merge process
	private static int merge(int[] arr, int l, int m, int r)
	{

		// Left subarray
		int[] l1 = Arrays.copyOfRange(arr, l, m + 1);

		// Right subarray
		int[] r1 = Arrays.copyOfRange(arr, m + 1, r + 1);

		int i = 0, j = 0, k = l, s = 0;

		while (i < l1.length && j < r1.length) {
			if (l1[i] <= r1[j])
				arr[k++] = l1[i++];
			else {
				arr[k++] = r1[j++];
				s = s + (m + 1) - (l + i);
			}
		}
		while (i < l1.length)
			arr[k++] = l1[i++];
		while (j < r1.length)
			arr[k++] = r1[j++];
		return s;
	}

	// Merge sort function
	private static int merge_sort(int[] arr, int l, int r)
	{

		// Keeps track of the inversion count at a
		// particular node of the recursion tree
		int count = 0;

		if (l < r) {
			int m = (l + r) / 2;

			

			count = count + merge_sort(arr, l, m);

			// Right subarray count
			count = count + merge_sort(arr, m + 1, r);

			// Merge count
			count = count + merge(arr, l, m, r);
		}

		return count;
	}
	
	
	public static void main(String[] args)
	{
		int n ;
 Scanner sc = new Scanner ( System.in ) ;
 System.out.println ( " Enter the total number of elements :  " ) ;
 n = sc.nextInt() ;
 int [] A = new int[ 100 ] ;
 System.out.println ( " Enter elements of the array :  " ) ;
 for ( int i = 0 ; i < n ; i++ )
 {
	 A[ i ] = sc.nextInt() ;
 }
 
System.out.println(" The total number of inversion counts possible is: " + merge_sort(A, 0, n-1)) ;
	}
}

上述程序的输出为

Enter number of elements present in the array: 10
 Enter array: 
9
7
6
1
4
12
2
3
0
6
  The total number of inversion counts possible is: 30

使用上述方法在 Python 编程语言中实现反转计数问题 -

# Python program to find the total number of inversion counts possible using the method 
# discussed above
# The program will print the count of the total number of inversions possible from an 
# random array 


def MS(arr, n):
	# A temp_arr is created to store
	# sorted array in merge function
	temp_arr = [0]*n
	return merge_sort(arr, temp_arr, 0, n-1)

# This Function will use MergeSort to count inversions


def merge_sort(arr, temp_arr, l, r):

	# A variable ic is used to store
	# inversion counts in each recursive call

	ic = 0

	


	if l < r:

		

		mid = (l + r)/2

		# It will calculate inversion
		# counts in the left subarray

		ic = ic +  merge_sort(arr, temp_arr, l, m)

		# It will calculate inversion
		# counts in the right subarray

		ic = ic + merge_sort(arr, temp_arr, m + 1, r)

		# It will merge two subarrays in
		# a sorted subarray

		ic = ic + merge(arr, temp_arr, l, m, r)
	return ic

# This function will merge two subarrays
# in a single sorted subarray


def merge(arr, temp, l, m, r):
	i = l	 # Starting index of left subarray
	j = m + 1 # Starting index of right subarray
	k = l	 # Starting index of to be sorted subarray
	ic = 0

	# Conditions are checked to make sure that
	# i and j don't exceed their
	# subarray limits.

	while i <= m and j <= r:

		

		if arr[i] <= arr[j]:
			temp[k] = arr[i]
			k = k + 1
			i = i + 1
		else:
			# Inversion will occur.
			temp[k] = arr[j]
			ic = ic + (m-i + 1)
			k = k + 1
			j = j + 1

	# Copy the remaining elements of left
	# subarray into temporary array
	while i <= m:
		temp[k] = arr[i]
		k = k + 1
		i = i + 1

	# Copy the remaining elements of right
	# subarray into temporary array
	while j <= r:
		temp[k] = arr[j]
		k = k + 1
		j = j + 1

	# Copy the sorted subarray into Original array
	for n in range(l, r + 1):
		arr[n] = temp[n]

	return ic


# Given array is
arr = [1, 2, 6, 4, 5, 3, 2, 1]
n = len(arr)
result = MS(arr, n)
print("The total number of inversions possible from the above array are :  ", result)

上述程序的输出为

The total number of inversions possible from the above array is: 15

使用上述方法在 C# 编程语言中实现反转计数问题 -

/* C# program to find the total number of inversion counts possible using the method discussed above*/
/* The program will print the count of the total number of inversions possible from a random array */
using System;
public class Main {

	

	static int MS(int[] arr, int n)
	{
		int[] temp = new int[n];
		return merge_sort(arr, temp, 0, n - 1);
	}

	static int merge_sort(int[] arr, int[] temp, int l, int r)
	{
		int mid, ic = 0;
		if (r > l) {
			

			m = (r + l) / 2;

			

			ic = ic + merge_sort(arr, temp, l, m);
			ic = ic + merge_sort(arr, temp, m + 1, r);

			/*Merge the two parts*/
			ic = ic + merge(arr, temp, l, m + 1, r);
		}
		return ic;
	}

	

	static int merge(int[] arr, int[] temp, int l, int m, int r)
	{
		int i, j, k;
		int ic = 0;

		i = l;                    /* i is index for left subarray*/
		j = m;                   /* j is index for right subarray*/
		k = l;                   /* k is index for resultant merged
					subarray*/
		while ((i <= m - 1) && (j <= r)) {
			if (arr[i] <= arr[j]) {
				temp[k++] = arr[i++];
			}
			else {
				temp[k++] = arr[j++];
				ic = ic + (m - i);
			}
		}

		/* Copy the remaining elements of left subarray
	(if there are any) to temp*/
		while (i <= m - 1)
			temp[k++] = arr[i++];

		/* Copy the remaining elements of right subarray
	(if there are any) to temp*/
		while (j <= r)
			temp[k++] = arr[j++];

		/*Coping back the merged elements into the original array*/
		for (i = l; i <= r; i++)
			arr[i] = temp[i] ;

		return ic ;
	}
	public static void Main()
	{
		int[] arr = new int[] { 11, 2, 16, 4, 5 , 3, 1, 0};
		Console.Write("The total number of inversions possible from the above array are " + MS(arr, 8));
	}
}

上述程序的输出为

The total number of inversions possible from the above array is: 22

使用上述方法在 JavaScript 编程语言中实现反转计数问题 -

<script>
	function merge(arr, l, m, r)
	{
	
		// Left subarray
		let left = [];
		for(let i = l; i < m + 1; i++)
		{
			left.push(arr[i]);
			
		}
		
		// Right subarray
		let right = [];
		for(let i = m + 1; i < r + 1; i++)
		{
			right.push(arr[i]);
		}
		let i = 0, j = 0, k = l, s = 0;
		while (i < left.length && j < right.length)
		{
			if (left[i] <= right[j])
			{
				arr[k++] = left[i++];
			}
			else
			{
				arr[k++] = right[j++];
				s = s + (m + 1) - (l + i);
			}
		}
		while (i < left.length)
		{
			arr[k++] = left[i++];
		}
		while (j < right.length)
		{
			arr[k++] = right[j++];
		}
		return s;
	}
	
	// Merge sort function
	function merge_sort (arr, l, r)
	{
		
		

		let count = 0;
		if (l < r)
		{
			let m = Math.floor((l + r) / 2);
			
			
			ic = ic + merge_sort (arr, l, m);
			
			// Right subarray count
			ic = ic + merge_sort (arr, m + 1, r);
			
			// Merge count
			ic = ic + merge(arr, l, m, r);
		}
		return ic;
	}
	
		let a= new Array(1, 20, 6, 4, 5 );
	document.write(merge_sort (a, 0, a.length - 1));
	
	
</script>

上述程序的输出为

The total number of inversions possible from the above array is: 5

正如我们已经看到了使用简单方法实现反转计数问题，现在我们将分析上述问题以及上述实现方法的空间和时间复杂度。

上述简单方法解决反转计数问题的时复杂度 -

为了分析时间复杂度，我们将检查代码的每一行并找出每一行的复杂度。因此，使用归并排序方法，程序的时复杂度将变为 n*log(n)，因为在这里，我们需要在循环内进行 n 次比较，用于排序后的数组合并，以及 log(n) 的复杂度用于调用 mergesort 函数，在该函数中，我们将同时调用两次相同的函数，因此最终结果将为 log(n) 时间。

T ( n ) = 2 T ( n / 2 ) + O ( n )

最终时间复杂度为 T ( n ) = O ( n * log ( n ) )。

在这里，我们观察到，我们了解到在最佳情况、最坏情况和平均情况的所有三种情况下的时间复杂度将保持不变，即 T ( n ) = O ( n * log ( n ) )。

上述简单方法解决反转计数问题的空间复杂度 -

要查找空间复杂度，我们需要观察程序并分析存储所有变量所需的空间；当我们注意到程序时，我们将观察到我们需要额外的空间来容纳 n 个元素的临时数组。

S ( n ) = O ( n )

下一个主题数据结构中的表达式树

逆序数

什么是反转计数？

用于解决上述反转计数问题的常用方法

使用简单方法解决反转计数问题

解决反转计数问题的实现算法 -

使用上述方法在 C 编程语言中实现反转计数问题 -

使用上述方法在 C++ 编程语言中实现反转计数问题 -

使用上述方法在 Java 编程语言中实现反转计数问题 -

使用上述方法在 Python 编程语言中实现反转计数问题 -

使用上述方法在 C# 编程语言中实现反转计数问题 -

上述简单方法解决反转计数问题的时复杂度 -

上述简单方法解决反转计数问题的空间复杂度 -

使用归并排序方法解决反转计数问题

解决反转计数问题的实现算法 -

使用上述方法在 C 编程语言中实现反转计数问题 -

使用上述方法在 C++ 编程语言中实现反转计数问题 -

使用上述方法在 JAVA 编程语言中实现反转计数问题 -

使用上述方法在 Python 编程语言中实现反转计数问题 -

使用上述方法在 C# 编程语言中实现反转计数问题 -

使用上述方法在 JavaScript 编程语言中实现反转计数问题 -

上述简单方法解决反转计数问题的时复杂度 -

上述简单方法解决反转计数问题的空间复杂度 -

联系信息

关注我们

教程

面试题

在线编译器

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

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

逆序数

什么是反转计数？

用于解决上述反转计数问题的常用方法

使用简单方法解决反转计数问题

解决反转计数问题的实现算法 -

使用上述方法在 C 编程语言中实现反转计数问题 -

使用上述方法在 C++ 编程语言中实现反转计数问题 -

使用上述方法在 Java 编程语言中实现反转计数问题 -

使用上述方法在 Python 编程语言中实现反转计数问题 -

使用上述方法在 C# 编程语言中实现反转计数问题 -

上述简单方法解决反转计数问题的时复杂度 -

上述简单方法解决反转计数问题的空间复杂度 -

使用归并排序方法解决反转计数问题

解决反转计数问题的实现算法 -

使用上述方法在 C 编程语言中实现反转计数问题 -

使用上述方法在 C++ 编程语言中实现反转计数问题 -

使用上述方法在 JAVA 编程语言中实现反转计数问题 -

使用上述方法在 Python 编程语言中实现反转计数问题 -

使用上述方法在 C# 编程语言中实现反转计数问题 -

使用上述方法在 JavaScript 编程语言中实现反转计数问题 -

上述简单方法解决反转计数问题的时复杂度 -

上述简单方法解决反转计数问题的空间复杂度 -

相关帖子

N 元树的序列化和反序列化

树中的第 K 个祖先

展平链表

检查表达式中的括号是否平衡 (格式正确性)

数据结构中的时间复杂度

数据结构中栈的局限性

应用操作以最大化频率分数

DS 中的二叉树遍历

打印字符串中的所有不同字符

N 元树的 DFS (无环图) 表示为邻接表

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器