思路一样,但就是跑不正确
来源:3-9 归并排序和快速排序的衍生问题
慕勒3376870
2021-07-02
老师这是我的代码:
public class FindDisorderedNumbers {
public static void main(String[] args) {
int[] arr = {1,0,2,3,4,5,6,7,8,9};
int m = 0;
for( int i = 0 ; i < arr.length ; i++ ) {
for( int j = i + 1 ; j < arr.length ; j++ ) {
if(arr[i] > arr[j])
m++;
}
}
int n = findDisorderedNumbers(arr);
System.out.println("逆序对的个数为:" + n);
System.out.println("慢方法求得的逆序对的个数为:"+ m);
}
private static int findDisorderedNumbers(int[] arr) {
return find(arr,0,arr.length - 1);
}
private static int find(int[] arr, int left, int right) {
if(left >= right)
return 0;
int mid =( left + right )/2;
int m = find(arr,left,mid);
int n = find(arr,mid+1,right);
int p = merge(arr,left,mid,right);
return m + n + p;
}
private static int merge(int[] arr, int left, int mid, int right) {
int[] aux = new int[right - left + 1];
for( int i = left ; i <= right ; i++ ) {
aux[ i - left ] = arr[left];
}
int i=left,j=mid+1,n=0;
for( int k = left ; k <= right ; k++) {
if(i > mid) {
arr[k] = aux[j - left];
j++;
}else if(j > right) {
arr[k] = aux[i - left];
i++;
}else if(aux[i - left] < aux[j - left]) {
arr[k] = aux[i - left];
i++;
}else {
arr[k] = aux[j - left];
j++;
n += mid - i + 1;
System.out.println("(mid - i + 1) is :" + (mid - i + 1));
System.out.println("the number of n is :"+ n);
}
}
System.out.println("---------------------------------");
return n;
}
}
1回答
-
liuyubobobo
2021-07-03
你这样给我贴一堆代码没有一点注释和思路说明,我也不能给你调代码。
对于 {3, 1, 2} 这个测试用例,你的程序的结果就是错误。这个测试用例只有三个数字,包括两个逆序对,(3, 1) 和 (3, 2),你的程序给出了三个。这个测试用例足够小,请使用这个测试用例去做单步跟踪,看看你的代码到底在哪里数出了第三个逆序对?在这一步各个变量的值是什么?但应该是什么?程序哪里和自己想的不一样?为什么不一样?是自己的想法有问题,还是落实到程序中有问题?
这是一种重要的学习方法。进步就在这个过程中。
继续加油!:)
012021-07-03
相似问题