思路一样,但就是跑不正确

来源: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),你的程序给出了三个。这个测试用例足够小,请使用这个测试用例去做单步跟踪,看看你的代码到底在哪里数出了第三个逆序对?在这一步各个变量的值是什么?但应该是什么?程序哪里和自己想的不一样?为什么不一样?是自己的想法有问题,还是落实到程序中有问题?


这是一种重要的学习方法。进步就在这个过程中。


课程的参考代码,你也可以做比对用:https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28Java%29/Optional-04-Inversion-Number/src/bobo/algo/InversionCount.java


继续加油!:)

0
1
慕勒3376870
非常感谢老师的建议,通过单步追踪我发现是我在复制数组的过程中将赋的值的索引写错了,老师的建议非常有用!^_^
2021-07-03
共1条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程