计算给定数组中大小为 3 的反转数量
原文： https://www.geeksforgeeks.org/count-inversions-of-size-three-in-a-give-array/
给定大小为n的数组arr[]。 如果a[i] > a[j] > a[k]和i < j < k，则三个元素arr[i]，arr[j]和arr[k]形成大小为 3 的反转。 查找大小为 3 的反转总数。
示例：
Input: {8, 4, 2, 1}
Output: 4
The four inversions are (8,4,2), (8,4,1), (4,2,1) and (8,2,1).
Input: {9, 6, 4, 5, 8}
Output: 2
The two inversions are {9, 6, 4} and {9, 6, 5}
我们已经讨论了通过归并排序，自平衡 BST 和 BIT 进行的大小为 2 的反转计数。
简单方法：循环搜索i，j和k的所有可能值，并检查条件a[i] > a[j] > a[k]和i < j < k。
C++
// A Simple C++ O(n^3) program to count inversions of size 3
#include<bits/stdc++.h>
using namespace std;
// Returns counts of inversions of size three
int getInvCount(int arr[],int n)
{
int invcount = 0; // Initialize result
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;
}
// Driver program to test above function
int main()
{
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Inversion Count : " << getInvCount(arr, n);
return 0;
}
Java
// A simple Java implementation to count inversion of size 3
class Inversion{
// returns count of inversion of size 3
int getInvCount(int arr[], int n)
{
int invcount = 0; // initialize result
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;
}
// driver program to test above function
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 : " +
inversion.getInvCount(arr, n));
}
}
// This code is contributed by Mayank Jaiswal
Python
# A simple python O(n^3) program
# to count inversions of size 3
# Returns counts of inversions
# of size threee
def getInvCount(arr):
n = len(arr)
invcount = 0 #Initialize result
for i in range(0,n-1):
for j in range(i+1 , n):
if arr[i] > arr[j]:
for k in range(j+1 , n):
if arr[j] > arr[k]:
invcount += 1
return invcount
# Driver program to test above function
arr = [8 , 4, 2 , 1]
print "Inversion Count : %d" %(getInvCount(arr))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// A simple C# implementation to
// count inversion of size 3
using System;
class GFG {
// returns count of inversion of size 3
static int getInvCount(int []arr, int n)
{
// initialize result
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;
}
// Driver Code
public static void Main()
{
int []arr = new int[] {8, 4, 2, 1};
int n = arr.Length;
Console.WriteLine("Inversion count : " +
getInvCount(arr, n));
}
}
// This code is contributed by anuj_67\.
PHP
<?php
// A O(n^2) PHP program to
// count inversions of size 3
// Returns count of
// inversions of size 3
function getInvCount($arr, $n)
{
// Initialize result
$invcount = 0;
for ($i = 1; $i < $n - 1; $i++)
{
// Count all smaller elements
// on right of arr[i]
$small = 0;
for($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$small++;
// Count all greater elements
// on left of arr[i]
$great = 0;
for($j = $i - 1; $j >= 0; $j--)
if ($arr[$i] < $arr[$j])
$great++;
// Update inversion count by
// adding all inversions
// that have arr[i] as
// middle of three elements
$invcount += $great * $small;
}
return $invcount;
}
// Driver Code
$arr = array(8, 4, 2, 1);
$n = sizeof($arr);
echo "Inversion Count : "
, getInvCount($arr, $n);
// This code is contributed m_kit
?>
Output:
Inversion Count : 4
这种方法的时间复杂度：O(n ^ 3)。
更好的方法：
如果我们将每个元素arr[i]视为反演的中间元素，并找到所有大于a[i]且其索引小于i的数字，找到所有小于a[i]且索引大于i的数字，则可以降低复杂度。 我们将大于a[i]的元素数量乘以小于a[i]的元素数量，并将其添加到结果中。
以下是该想法的实现。
C++
// A O(n^2) C++ program to count inversions of size 3
#include<bits/stdc++.h>
using namespace std;
// Returns count of inversions of size 3
int getInvCount(int arr[], int n)
{
int invcount = 0; // Initialize result
for (int i=1; i<n-1; i++)
{
// Count all smaller elements on right of arr[i]
int small = 0;
for (int j=i+1; j<n; j++)
if (arr[i] > arr[j])
small++;
// Count all greater elements on left of arr[i]
int great = 0;
for (int j=i-1; j>=0; j--)
if (arr[i] < arr[j])
great++;
// Update inversion count by adding all inversions
// that have arr[i] as middle of three elements
invcount += great*small;
}
return invcount;
}
// Driver program to test above function
int main()
{
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Inversion Count : " << getInvCount(arr, n);
return 0;
}
Java
// A O(n^2) Java program to count inversions of size 3
class Inversion {
// returns count of inversion of size 3
int getInvCount(int arr[], int n)
{
int invcount = 0; // initialize result
for (int i=0 ; i< n-1; i++)
{
// count all smaller elements on right of arr[i]
int small=0;
for (int j=i+1; j<n; j++)
if (arr[i] > arr[j])
small++;
// count all greater elements on left of arr[i]
int great = 0;
for (int j=i-1; j>=0; j--)
if (arr[i] < arr[j])
great++;
// update inversion count by adding all inversions
// that have arr[i] as middle of three elements
invcount += great*small;
}
return invcount;
}
// driver program to test above function
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 : " +
inversion.getInvCount(arr, n));
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# A O(n^2) Python3 program to
# count inversions of size 3
# Returns count of inversions
# of size 3
def getInvCount(arr, n):
# Initialize result
invcount = 0
for i in range(1,n-1):
# Count all smaller elements
# on right of arr[i]
small = 0
for j in range(i+1 ,n):
if (arr[i] > arr[j]):
small+=1
# Count all greater elements
# on left of arr[i]
great = 0;
for j in range(i-1,-1,-1):
if (arr[i] < arr[j]):
great+=1
# Update inversion count by
# adding all inversions that
# have arr[i] as middle of
# three elements
invcount += great * small
return invcount
# Driver program to test above function
arr = [8, 4, 2, 1]
n = len(arr)
print("Inversion Count :",getInvCount(arr, n))
# This code is Contributed by Smitha Dinesh Semwal
C
// A O(n^2) Java program to count inversions
// of size 3
using System;
public class Inversion {
// returns count of inversion of size 3
static int getInvCount(int []arr, int n)
{
int invcount = 0; // initialize result
for (int i = 0 ; i < n-1; i++)
{
// count all smaller elements on
// right of arr[i]
int small = 0;
for (int j = i+1; j < n; j++)
if (arr[i] > arr[j])
small++;
// count all greater elements on
// left of arr[i]
int great = 0;
for (int j = i-1; j >= 0; j--)
if (arr[i] < arr[j])
great++;
// update inversion count by
// adding all inversions that
// have arr[i] as middle of
// three elements
invcount += great * small;
}
return invcount;
}
// driver program to test above function
public static void Main()
{
int []arr = new int[] {8, 4, 2, 1};
int n = arr.Length;
Console.WriteLine("Inversion count : "
+ getInvCount(arr, n));
}
}
// This code has been contributed by anuj_67\.
PHP
<?php
// A O(n^2) PHP program to count
// inversions of size 3
// Returns count of
// inversions of size 3
function getInvCount($arr, $n)
{
// Initialize result
$invcount = 0;
for ($i = 1; $i < $n - 1; $i++)
{
// Count all smaller elements
// on right of arr[i]
$small = 0;
for ($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$small++;
// Count all greater elements
// on left of arr[i]
$great = 0;
for ($j = $i - 1; $j >= 0; $j--)
if ($arr[$i] < $arr[$j])
$great++;
// Update inversion count by
// adding all inversions that
// have arr[i] as middle of
// three elements
$invcount += $great * $small;
}
return $invcount;
}
// Driver Code
$arr = array (8, 4, 2, 1);
$n = sizeof($arr);
echo "Inversion Count : " ,
getInvCount($arr, $n);
// This code is contributed by m_kit
?>
输出：
Inversion Count : 4
这种方法的时间复杂度：O(n ^ 2)。
二元索引树方法：
与大小为 2 的反转类似，我们可以使用二叉索引树来找到大小为 3 的反转。强烈建议首先参考以下文章。
这个想法类似于上面的方法。 我们计算所有元素的较大元素和较小元素的数量，然后将great[]乘以small[]并将其添加到结果中。
解决方案：
-
为了找出索引中较小元素的数量，我们从
n-1迭代到 0。对于每个元素a[i]，我们计算a[i] - 1的getSum()函数，该函数给出元素的数量直到a[i] - 1。 -
为了找出索引中更大元素的数量，我们从 0 迭代到
n-1。 对于每个元素a[i]，我们通过getSum()计算直到a[i]的数目之和（总和小于或等于a[i]），然后从i中减去它（因为i是该点之前元素的总数），这样我们就可以得到大于a[i]的元素数量。
就像我们对大小为 2 的反转所做的一样，这里我们还将输入数组转换为值从 1 到n的数组，以便 BIT 的大小保持为O(n)，并且getSum()和update()函数需要O(log n)时间。 例如，我们将arr[] = {7, -90, 100, 1}转换为arr[] = {3, 1, 4, 2}。
以下是上述想法的实现。
C
// C++ program to count inversions of size three using
// Binary Indexed Tree
#include<bits/stdc++.h>
using namespace std;
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
int sum = 0; // Initialize result
// Traverse ancestors of BITree[index]
while (index > 0)
{
// Add current element of BITree to sum
sum += BITree[index];
// Move index to parent node in getSum View
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
// Traverse all ancestors and add 'val'
while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;
// Update index to that of parent in update View
index += index & (-index);
}
}
// Converts an array to an array with values from 1 to n
// and relative order of smaller and greater elements remains
// same. For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 ,2 }
void convert(int arr[], int n)
{
// Create a copy of arrp[] in temp and sort the temp array
// in increasing order
int temp[n];
for (int i=0; i<n; i++)
temp[i] = arr[i];
sort(temp, temp+n);
// Traverse all array elements
for (int i=0; i<n; i++)
{
// lower_bound() Returns pointer to the first element
// greater than or equal to arr[i]
arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
}
}
// Returns count of inversions of size three
int getInvCount(int arr[], int n)
{
// Convert arr[] to an array with values from 1 to n and
// relative order of smaller and greater elements remains
// same. For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 ,2 }
convert(arr, n);
// Create and initialize smaller and greater arrays
int greater1[n], smaller1[n];
for (int i=0; i<n; i++)
greater1[i] = smaller1[i] = 0;
// Create and initialize an array to store Binary
// Indexed Tree
int BIT[n+1];
for (int i=1; i<=n; i++)
BIT[i]=0;
for(int i=n-1; i>=0; i--)
{
smaller1[i] = getSum(BIT, arr[i]-1);
updateBIT(BIT, n, arr[i], 1);
}
// Reset BIT
for (int i=1; i<=n; i++)
BIT[i] = 0;
// Count greater elements
for (int i=0; i<n; i++)
{
greater1[i] = i - getSum(BIT,arr[i]);
updateBIT(BIT, n, arr[i], 1);
}
// Compute Inversion count using smaller[] and
// greater[].
int invcount = 0;
for (int i=0; i<n; i++)
invcount += smaller1[i]*greater1[i];
return invcount;
}
// Driver program to test above function
int main()
{
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Inversion Count : " << getInvCount(arr, n);
return 0;
}
Java
// Java program to count inversions of size three using
// Binary Indexed Tree
import java.util.Arrays;
class BinaryTree {
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index) {
int sum = 0; // Initialize result
// Traverse ancestors of BITree[index]
while (index > 0) {
// Add current element of BITree to sum
sum += BITree[index];
// Move index to parent node in getSum View
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index Tree (BITree) at given
// index in BITree. The given value 'val' is added to
// BITree[i] and all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val) {
// Traverse all ancestors and add 'val'
while (index <= n) {
// Add 'val' to current node of BI Tree
BITree[index] += val;
// Update index to that of parent in update View
index += index & (-index);
}
}
// Converts an array to an array with values from 1 to n
// and relative order of smaller and greater elements remains
// same. For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 ,2 }
void convert(int arr[], int n) {
// Create a copy of arrp[] in temp and sort the temp array
// in increasing order
int temp[]= new int[n];
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
}
Arrays.sort(temp);
// Traverse all array elements
for (int i = 0; i < n; i++) {
// lower_bound() Returns pointer to the first element
// greater than or equal to arr[i]
arr[i] = Arrays.binarySearch(temp, arr[i]) + 1;
}
}
// Returns count of inversions of size three
int getInvCount(int arr[], int n) {
// Convert arr[] to an array with values from 1 to n and
// relative order of smaller and greater elements remains
// same. For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 ,2 }
convert(arr, n);
// Create and initialize smaller and greater arrays
int greater1[]= new int[n];
int smaller1[]= new int[n];
for (int i = 0; i < n; i++) {
greater1[i] = smaller1[i] = 0;
}
// Create and initialize an array to store Binary
// Indexed Tree
int BIT[]= new int[n+1];
for (int i = 1; i <= n; i++) {
BIT[i] = 0;
}
for (int i = n - 1; i >= 0; i--) {
smaller1[i] = getSum(BIT, arr[i] - 1);
updateBIT(BIT, n, arr[i], 1);
}
// Reset BIT
for (int i = 1; i <= n; i++) {
BIT[i] = 0;
}
// Count greater elements
for (int i = 0; i < n; i++) {
greater1[i] = i - getSum(BIT, arr[i]);
updateBIT(BIT, n, arr[i], 1);
}
// Compute Inversion count using smaller[] and
// greater[].
int invcount = 0;
for (int i = 0; i < n; i++) {
invcount += smaller1[i] * greater1[i];
}
return invcount;
}
// Driver program to test above function
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
int[] arr = new int[]{8, 4, 2, 1};
int n = arr.length;
System.out.print( "Inversion Count : " +
tree.getInvCount(arr, n));
}
}
// This code is contributed by Mayank Jaiswal
C
// C# program to count inversions
// of size three using Binary Indexed Tree
using System;
class GFG
{
// Returns sum of arr[0..index].
// This function assumes that
// the array is preprocessed and
// partial sums of array elements
// are stored in BITree[].
int getSum(int[] BITree, int index)
{
int sum = 0; // Initialize result
// Traverse ancestors of
// BITree[index]
while (index > 0)
{
// Add current element of
// BITree to sum
sum += BITree[index];
// Move index to parent node
// in getSum View
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value
// 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int[] BITree, int n,
int index, int val)
{
// Traverse all ancestors
// and add 'val'
while (index <= n)
{
// Add 'val' to current
// node of BI Tree
BITree[index] += val;
// Update index to that of
// parent in update View
index += index & (-index);
}
}
// Converts an array to an array
// with values from 1 to n and
// relative order of smaller and
// greater elements remains same.
// For example, {7, -90, 100, 1}
// is converted to {3, 1, 4 ,2 }
void convert(int[] arr, int n)
{
// Create a copy of arrp[] in
// temp and sort the temp array
// in increasing order
int[] temp = new int[n];
for (int i = 0; i < n; i++)
{
temp[i] = arr[i];
}
Array.Sort(temp);
// Traverse all array elements
for (int i = 0; i < n; i++)
{
// lower_bound() Returns pointer
// to the first element greater
// than or equal to arr[i]
arr[i] = Array.BinarySearch(temp,
arr[i]) + 1;
}
}
// Returns count of inversions
// of size three
int getInvCount(int[] arr, int n)
{
// Convert arr[] to an array with
// values from 1 to n and relative
// order of smaller and greater
// elements remains same. For
// example, {7, -90, 100, 1} is
// converted to {3, 1, 4 ,2 }
convert(arr, n);
// Create and initialize
// smaller and greater arrays
int[] greater1 = new int[n];
int[] smaller1 = new int[n];
for (int i = 0; i < n; i++)
{
greater1[i] = smaller1[i] = 0;
}
// Create and initialize an
// array to store Binary Indexed Tree
int[] BIT = new int[n + 1];
for (int i = 1; i <= n; i++)
{
BIT[i] = 0;
}
for (int i = n - 1; i >= 0; i--)
{
smaller1[i] = getSum(BIT,
arr[i] - 1);
updateBIT(BIT, n, arr[i], 1);
}
// Reset BIT
for (int i = 1; i <= n; i++)
{
BIT[i] = 0;
}
// Count greater elements
for (int i = 0; i < n; i++)
{
greater1[i] = i - getSum(BIT,
arr[i]);
updateBIT(BIT, n, arr[i], 1);
}
// Compute Inversion count using
// smaller[] and greater[].
int invcount = 0;
for (int i = 0; i < n; i++)
{
invcount += smaller1[i] *
greater1[i];
}
return invcount;
}
// Driver Code
public static void Main()
{
GFG tree = new GFG();
int[] arr = new int[]{8, 4, 2, 1};
int n = arr.Length;
Console.Write( "Inversion Count : " +
tree.getInvCount(arr, n));
}
}
// This code is contributed
// by ChitraNayal
Python3
# Python3 program to count inversions of
# size three using Binary Indexed Tree
# Returns sum of arr[0..index]. This function
# assumes that the array is preprocessed and
# partial sums of array elements are stored
# in BITree[].
def getSum(BITree, index):
sum = 0 # Initialize result
# Traverse ancestors of BITree[index]
while (index > 0):
# Add current element of
# BITree to sum
sum += BITree[index]
# Move index to parent node
# in getSum View
index -= index & (-index)
return sum
# Updates a node in Binary Index Tree
# (BITree) at given index in BITree.
# The given value 'val' is added to BITree[i]
# and all of its ancestors in tree.
def updateBIT( BITree, n, index, val):
# Traverse all ancestors and add 'val'
while (index <= n):
# Add 'val' to current node of BI Tree
BITree[index] += val
# Update index to that of parent
# in update View
index += index & (-index)
# Converts an array to an array with values
# from 1 to n and relative order of smaller
# and greater elements remains same. For example,
# 7, -90, 100, 1 is converted to 3, 1, 4 ,2
def convert(arr, n) :
# Create a copy of arrp[] in temp and
# sort the temp array in increasing order
temp = [0] * n
for i in range(n):
temp[i] = arr[i]
temp = sorted(temp)
j = 1
# Traverse all array elements
for i in temp:
# lower_bound() Returns poer to
# the first element greater than
# or equal to arr[i]
arr[arr.index(i)] = j
j += 1
# Returns count of inversions of size three
def getInvCount( arr, n):
# Convert arr[] to an array with values
# from 1 to n and relative order of smaller
# and greater elements remains same. For example,
# 7, -90, 100, 1 is converted to 3, 1, 4 ,2
convert(arr, n)
# Create and initialize smaller and
# greater arrays
greater1 = [0] * n
smaller1 = [0] * n
for i in range(n):
greater1[i], smaller1[i] = 0, 0
# Create and initialize an array to
# store Binary Indexed Tree
BIT = [0] * (n + 1)
for i in range(1, n + 1):
BIT[i] = 0
for i in range(n - 1, -1, -1):
smaller1[i] = getSum(BIT, arr[i] - 1)
updateBIT(BIT, n, arr[i], 1)
# Reset BIT
for i in range(1, n + 1):
BIT[i] = 0
# Count greater elements
for i in range(n):
greater1[i] = i - getSum(BIT, arr[i])
updateBIT(BIT, n, arr[i], 1)
# Compute Inversion count using smaller[]
# and greater[].
invcount = 0
for i in range(n):
invcount += smaller1[i] * greater1[i]
return invcount
# Driver code
if __name__ =="__main__":
arr= [8, 4, 2, 1]
n = 4
print("Inversion Count : ",
getInvCount(arr, n))
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
输出：
Inversion Count : 4
时间复杂度：O(n log n)。
辅助空间：O(n)。
我们还可以使用自平衡二进制搜索树在左侧计算较大的元素，在右侧计算较小的元素。 该方法的时间复杂度也为O(n log n)，但基于 BIT 的方法易于实现。
版权属于：月萌API www.moonapi.com，转载请注明出处
