本文概述
- C ++
- C
- Java
- Python3
- C#
- 的PHP
- C ++
- C
- Java
- Python3
- C#
形式上讲, 如果a [i]> a [j]且i < j, 则两个元素a [i]和a [j]构成一个求逆
【算法(计算数组中的反转(逆序)S1(使用合并排序))】例子:
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)
方法1(简单)
- 方法:遍历数组, 并为每个索引找到数组右侧较小元素的数量。这可以使用嵌套循环来完成。对数组中所有索引的计数求和, 然后打印总和。
- 算法:
- 从头到尾遍历数组
- 对于每个元素, 使用另一个循环查找小于当前数量的元素数, 直到该索引为止。
- 总结每个索引的反转计数。
- 打印反转计数。
- 实现
// C++ program to Count Inversions
// in an array
#include <
bits/stdc++.h>
using namespace std;
int getInvCount( int arr[], int n)
{
int inv_count = 0;
for ( int i = 0;
i <
n - 1;
i++)
for ( int j = i + 1;
j <
n;
j++)
if (arr[i] >
arr[j])
inv_count++;
return inv_count;
}
// Driver Code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
cout <
<
" Number of inversions are "
<
<
getInvCount(arr, n);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C program to Count
// Inversions in an array
#include <
stdio.h>
#include <
stdlib.h>
int getInvCount( int arr[], int n)
{
int inv_count = 0;
for ( int i = 0;
i <
n - 1;
i++)
for ( int j = i + 1;
j <
n;
j++)
if (arr[i] >
arr[j])
inv_count++;
return inv_count;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( " Number of inversions are %d \n" , getInvCount(arr, n));
return 0;
}
Java
// Java program to count
// inversions in an array
class Test {
static int arr[] = new int [] { 1 , 20 , 6 , 4 , 5 };
static int getInvCount( int n)
{
int inv_count = 0 ;
for ( int i = 0 ;
i <
n - 1 ;
i++)
for ( int j = i + 1 ;
j <
n;
j++)
if (arr[i] >
arr[j])
inv_count++;
return inv_count;
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.println( "Number of inversions are "
+ getInvCount(arr.length));
}
}
Python3
# Python3 program to count
# inversions in an array
def getInvCount(arr, n):
inv_count = 0
for i in range (n):
for j in range (i + 1 , n):
if (arr[i] >
arr[j]):
inv_count + = 1
return inv_count
# Driver Code
arr = [ 1 , 20 , 6 , 4 , 5 ]
n = len (arr)
print ( "Number of inversions are" , getInvCount(arr, n))
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to count inversions
// in an array
using System;
using System.Collections.Generic;
class GFG {
static int [] arr = new int [] { 1, 20, 6, 4, 5 };
static int getInvCount( int n)
{
int inv_count = 0;
for ( int i = 0;
i <
n - 1;
i++)
for ( int j = i + 1;
j <
n;
j++)
if (arr[i] >
arr[j])
inv_count++;
return inv_count;
}
// Driver code
public static void Main()
{
Console.WriteLine( "Number of "
+ "inversions are "
+ getInvCount(arr.Length));
}
}
// This code is contributed by Sam007
的PHP
<
?php
// PHP program to Count Inversions
// in an array
function getInvCount(&
$arr , $n )
{
$inv_count = 0;
for ( $i = 0;
$i <
$n - 1;
$i ++)
for ( $j = $i + 1;
$j <
$n ;
$j ++)
if ( $arr [ $i ] >
$arr [ $j ])
$inv_count ++;
return $inv_count ;
}
// Driver Code
$arr = array (1, 20, 6, 4, 5 );
$n = sizeof( $arr );
echo "Number of inversions are " , getInvCount( $arr , $n );
// This code is contributed by ita_c
?>
- 输出如下:
Number of inversions are 5
- 复杂度分析:
- 时间复杂度:O(n ^ 2), 需要两个嵌套循环才能从头到尾遍历数组, 因此时间复杂度为O(n ^ 2)
- 空间复杂:O(1), 不需要额外的空间。
- 方法:
假设数组左半边和右半边的反转次数(分别为inv1和inv2), 在Inv1 + Inv2中没有考虑哪些反转?答案是–在合并步骤中需要计算的反转数。因此, 要获得许多反转, 需要在左子数组, 右子数组和merge()中添加许多反转。
文章图片
- 怎么获得的merge()中的反转次数?
在合并过程中, 让我用于索引左子数组, 让j用于右子数组。在merge()的任何步骤中, 如果a [i]大于a [j], 则存在(mid – i)个反转。因为左子数组和右子数组已排序, 所以左子数组中的所有其余元素(a [i + 1], a [i + 2]…a [mid])将大于a [j]
文章图片
- 完整图片:
文章图片
- 算法:
- 这个想法类似于合并排序, 将数组分成两个相等或几乎相等的两半, 直到达到基本情况为止。
- 创建一个函数合并, 计算合并数组的两半时的反转次数, 创建两个索引i和j, i是上半部分的索引, j是下半部分的索引。如果a [i]大于a [j], 则存在(mid – i)个反演。因为左子数组和右子数组已排序, 所以左子数组中的所有其余元素(a [i + 1], a [i + 2]…a [mid])将大于a [j]。
- 创建一个递归函数, 将数组分成两半, 然后求和前一半的求反数??, 再求后一半的求反数??, 然后将二者合并, 求出答案。
- 递归的基本情况是在给定的一半中只有一个元素。
- 打印答案
- 实现
// C++ program to Count
// Inversions in an array
// using Merge Sort
#include <
bits/stdc++.h>
using namespace std;
int _mergeSort( int arr[], int temp[], int left, int right);
int merge( int arr[], int temp[], int left, int mid, int right);
/* This function sorts the
input array and returns the
number of inversions in the array */
int mergeSort( int arr[], int array_size)
{
int temp[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive function
that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort( int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right >
left) {
/* Divide the array into two parts and
call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left) / 2;
/* Inversion count will be sum of
inversions in left-part, right-part
and number of inversions in merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays
and returns inversion count in the arrays.*/
int merge( int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left;
/* i is index for left subarray*/
j = mid;
/* j is index for right subarray*/
k = left;
/* k is index for resultant merged subarray*/
while ((i <
= mid - 1) &
&
(j <
= right)) {
if (arr[i] <
= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/* this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (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 <
= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left;
i <
= right;
i++)
arr[i] = temp[i];
return inv_count;
}
// Driver code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
int ans = mergeSort(arr, n);
cout <
<
" Number of inversions are " <
<
ans;
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to Count
// Inversions in an array
// using Merge Sort
#include <
stdio.h>
#include <
stdlib.h>
int _mergeSort( int arr[], int temp[], int left, int right);
int merge( int arr[], int temp[], int left, int mid, int right);
/* This function sorts the input array and returns the
number of inversions in the array */
int mergeSort( int arr[], int array_size)
{
int * temp = ( int *) malloc ( sizeof ( int ) * array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive function that sorts the input
array and returns the number of inversions in the array.
*/
int _mergeSort( int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right >
left) {
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of the parts */
mid = (right + left) / 2;
/* Inversion count will be the sum of inversions in
left-part, right-part and number of inversions in
merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays and returns inversion
count in the arrays.*/
int merge( int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left;
/* i is index for left subarray*/
j = mid;
/* j is index for right subarray*/
k = left;
/* k is index for resultant merged subarray*/
while ((i <
= mid - 1) &
&
(j <
= right)) {
if (arr[i] <
= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (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 <
= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left;
i <
= right;
i++)
arr[i] = temp[i];
return inv_count;
}
/* Driver program to test above functions */
int main( int argv, char ** args)
{
int arr[] = { 1, 20, 6, 4, 5 };
printf ( " Number of inversions are %d \n" , mergeSort(arr, 5));
getchar ();
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
public class GFG {
// Function to count the number of inversions
// during the merge process
private static int mergeAndCount( int [] arr, int l, int m, int r)
{
// Left subarray
int [] left = Arrays.copyOfRange(arr, l, m + 1 );
// Right subarray
int [] right = Arrays.copyOfRange(arr, m + 1 , r + 1 );
int i = 0 , j = 0 , k = l, swaps = 0 ;
while (i <
left.length &
&
j <
right.length)
{
if (left[i] <
= right[j])
arr[k++] = left[i++];
else {
arr[k++] = right[j++];
swaps += (m + 1 ) - (l + i);
}
}
return swaps;
}
// Merge sort function
private static int mergeSortAndCount( 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 ;
// Total inversion count = left subarray count
// + right subarray count + merge count
// Left subarray count
count += mergeSortAndCount(arr, l, m);
// Right subarray count
count += mergeSortAndCount(arr, m + 1 , r);
// Merge count
count += mergeAndCount(arr, l, m, r);
}
return count;
}
// Driver code
public static void main(String[] args)
{
int [] arr = { 1 , 20 , 6 , 4 , 5 };
System.out.println(mergeSortAndCount(arr, 0 , arr.length - 1 ));
}
}
// This code is contributed by Pradip Basak
Python3
# Python 3 program to count inversions in an array
# Function to Use Inversion Count
def mergeSort(arr, n):
# A temp_arr is created to store
# sorted array in merge function
temp_arr = [ 0 ] * n
return _mergeSort(arr, temp_arr, 0 , n - 1 )
# This Function will use MergeSort to count inversions
def _mergeSort(arr, temp_arr, left, right):
# A variable inv_count is used to store
# inversion counts in each recursive call
inv_count = 0
# We will make a recursive call if and only if
# we have more than one elements
if left <
right:
# mid is calculated to divide the array into two subarrays
# Floor division is must in case of python
mid = (left + right) / / 2
# It will calculate inversion
# counts in the left subarray
inv_count + = _mergeSort(arr, temp_arr, left, mid)
# It will calculate inversion
# counts in right subarray
inv_count + = _mergeSort(arr, temp_arr, mid + 1 , right)
# It will merge two subarrays in
# a sorted subarray
inv_count + = merge(arr, temp_arr, left, mid, right)
return inv_count
# This function will merge two subarrays
# in a single sorted subarray
def merge(arr, temp_arr, left, mid, right):
i = left# Starting index of left subarray
j = mid + 1 # Starting index of right subarray
k = left# Starting index of to be sorted subarray
inv_count = 0
# Conditions are checked to make sure that
# i and j don't exceed their
# subarray limits.
while i <
= mid and j <
= right:
# There will be no inversion if arr[i] <
= arr[j]
if arr[i] <
= arr[j]:
temp_arr[k] = arr[i]
k + = 1
i + = 1
else :
# Inversion will occur.
temp_arr[k] = arr[j]
inv_count + = (mid - i + 1 )
k + = 1
j + = 1
# Copy the remaining elements of left
# subarray into temporary array
while i <
= mid:
temp_arr[k] = arr[i]
k + = 1
i + = 1
# Copy the remaining elements of right
# subarray into temporary array
while j <
= right:
temp_arr[k] = arr[j]
k + = 1
j + = 1
# Copy the sorted subarray into Original array
for loop_var in range (left, right + 1 ):
arr[loop_var] = temp_arr[loop_var]return inv_count
# Driver Code
# Given array is
arr = [ 1 , 20 , 6 , 4 , 5 ]
n = len (arr)
result = mergeSort(arr, n)
print ( "Number of inversions are" , result)
# This code is contributed by ankush_953
C#
// C# implementation of counting the
// inversion using merge sort
using System;
public class Test {
/* This method sorts the input array and returns the
number of inversions in the array */
static int mergeSort( int [] arr, int array_size)
{
int [] temp = new int [array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive method that sorts the input
array and returns the number of inversions in the
array. */
static int _mergeSort( int [] arr, int [] temp, int left, int right)
{
int mid, inv_count = 0;
if (right >
left) {
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of the parts */
mid = (right + left) / 2;
/* Inversion count will be the sum of inversions
in left-part, right-part
and number of inversions in merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count
+= _mergeSort(arr, temp, mid + 1, right);
/*Merge the two parts*/
inv_count
+= merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
/* This method merges two sorted arrays and returns
inversion count in the arrays.*/
static int merge( int [] arr, int [] temp, int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left;
/* i is index for left subarray*/
j = mid;
/* j is index for right subarray*/
k = left;
/* k is index for resultant merged
subarray*/
while ((i <
= mid - 1) &
&
(j <
= right)) {
if (arr[i] <
= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (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 <
= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left;
i <
= right;
i++)
arr[i] = temp[i];
return inv_count;
}
// Driver method to test the above function
public static void Main()
{
int [] arr = new int [] { 1, 20, 6, 4, 5 };
Console.Write( "Number of inversions are "
+ mergeSort(arr, 5));
}
}
// This code is contributed by Rajput-Ji
- 输出如下:
Number of inversions are 5
- 复杂度分析:
- 时间复杂度:O(n log n), 使用的算法是分治法, 因此在每个级别中需要一个完整的数组遍历, 并且存在log n个级别, 因此时间复杂度为O(n log n)。
- 空间复杂:O(n), 临时数组。
计算数组中的反转设置2(使用自平衡BST)
使用C++ STL中的Set计数反转
计算数组中的反转第三组(使用BIT)
参考文献:
http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm
如果你在上述程序/算法或其他解决相同问题的方法中发现任何错误, 请发表评论。
推荐阅读
- 算法(重新排列数组使正负项交替出现,使用O(1)空间|S2)
- 算法题(如何计算从1到n的所有数字的数字总和())
- std::swap和std::vector::swap之间有什么区别()
- JavaScript如何使用正则表达式(用法示例)
- 云服务和云计算详细介绍和指南
- PHP如何使用gethostbyname()函数(用法示例)
- 如何打包Angular应用到生产环境()
- JavaScript中的控制台对象用法详细指南
- Scala函数基础(解析和用法示例)