给定数组中大小为 3 的计数反转的 Java 程序
原文:https://www . geeksforgeeks . org/Java-用于计算给定数组中三个大小的反转的程序/
给定大小为 n 的数组 arr[]。如果 a[i] > a[j] >a[k]和 i < j < k. Find total number of inversions of size 3. 的话，三个元素 arr[i]、arr[j]和 arr[k]形成大小为 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 讨论了大小二的反转计数。 简单方法:- 循环 I、j 和 k 的所有可能值，并检查条件 a[i] > a[j] > a[k]和 I<j<k
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
输出:
Inversion Count : 4
时间复杂度这个方法是:O(n^3) 更好的方法: 我们可以降低复杂度，如果我们把每个元素 arr[i]看作求逆的中间元素，找出所有大于 a[i]且指数小于 I 的数字，找出所有小于 a[i]且指数大于 I 的数字，我们把大于 a[i]的元素数乘以小于 a[i]的元素数，加到结果中。 下面是想法的实现。
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
输出:
Inversion Count : 4
时间复杂度这种方法:O(n^2) 二进制索引树方法: 像大小为 2 的逆矩阵一样，我们可以使用二进制索引树来寻找大小为 3 的逆矩阵。强烈建议先参考下面的文章。 使用 BIT 计算大小二的倒位，思路与上述方法类似。我们计算所有元素中较大元素和较小元素的数量，然后将较大的[]乘以较小的[]并将其添加到结果中。 解决方案:
- 为了找出索引中较小元素的数量，我们从 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]的元素数量。
更多细节请参考完整的文章计算给定数组中大小为三的反转！
版权属于：月萌API www.moonapi.com，转载请注明出处
