我想找到二维数组中可能的反转次数。我已经编写了这个程序,需要一些方法来加速它:
import java.io.*;
import java.util.*;
class Solution
{
static long merge(int[] array, int[] left, int[] right)
{
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length)
{
if (i == left.length)
{
array[i+j] = right[j];
j++;
}
else if (j == right.length)
{
array[i+j] = left[i];
i++;
}
else if (left[i] <= right[j])
{
array[i+j] = left[i];
i++;
}
else
{
array[i+j] = right[j];
count += left.length-i;
j++;
}
}
return count;
}
static long invCount(int[] array)
{
if (array.length < 2)
return 0;
int m = (array.length + 1) / 2;
int left[] = Arrays.copyOfRange(array, 0, m);
int right[] = Arrays.copyOfRange(array, m, array.length);
return invCount(left) + invCount(right) + merge(array, left, right);
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long inversions=0;
int[][] arr2=new int[n][n];
if(n<0)
{
System.out.println("0");
return;
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
arr2[i][j]=sc.nextInt();
//arr2[i][j]=arr[i][j];
}
long inv=0;
int counter=0;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
while(counter<n)
{
for(int z=counter;z<n;z++)
{
//System.out.println("comparing "+arr2[i][counter]+" with "+arr2[j][z]);
if(arr2[i][counter]>arr2[j][z])
inv++;
}
counter++;
//System.out.println("end while---------\n");
}
//System.out.println("Row change#########\n");
counter=0;
}
}
for (int i=0;i<n;i++)
inv=inv+invCount(arr2[i]);
System.out.println(inv);
}
}
这个程序可以优化吗?还是这个程序在某个地方出错了?我得到了 2 个测试用例的正确输出,它们是: 2D 数组的 4 个反转:
9 7
1 2
和 19 个二维数组的反演:
9 7 6
1 2 5
2 3 1
感谢帮助。:)