欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer51:数组中的逆序对

程序员文章站 2022-07-10 12:16:58
...

题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

eg:输入数组 7,5,6,4.共存在5个逆序对,{7,6},{7,5},{7,4},{6,4},{5,4}。

暴力法,即第一次遍历n个数的过程中,从n+1…往下,时间复杂度是O(n2)。

书上的更快的方法:即借助,归并排序的思想,将数组划分成为2个子数组,再在2个子数组的基础上继续划分为4个子数组,直到每个子数组中只含有1个数的时候,停止划分(这里应该是边界条件),继续判断逻辑
当含有2个子数组时,7大于5,count+1.6大于4的时候count+1.然后p1指向子数组{5,7}中的7,p2指向{4,6}中的6,并且再设立辅助数组,当p1>p2,时,count加上p2(包含p2本身)之前的所有元素个数。再将p1放入辅助数组中,p3指向当前元素,再p1,p3指针同时减1.再判断,p1>p2?,不大于,将p2直接放入辅助数组中,同时,p2,p3减1.当p1为空时,p2不为空,就直接将p2剩余的元素放入辅助数组就好了。

书上代码:

 public int InversePair(int[] array){

        int len = array.length;
        if(array == null || len <= 0){
            return 0;
        }
        return mergSort(array,0,len-1);
    }

    public int mergSort(int[] array,int start,int end){

        //就一条件
        if(start == end)
        {
            return 0;
        }
        int mid = (start + end) / 2;

        int left_count = mergSort(array,start,mid);

        int right_count = mergSort(array,mid+1,end);

        int i = mid,j = end;
        //新建了数组
        int[] copy =new int[end-start+1];

        int copy_index = end-start;

        int count = 0;

        while(i >= start && j >= mid + 1){
            if(array[i] > array[j]){
                copy[copy_index--] = array[i--];
                count += j-mid;

            }else{
                copy[copy_index--] = array[j--];
            }

        }
        while(i >= start){
            copy[copy_index--] = array[i--];
        }

        while(j >= mid+1){
            copy[copy_index--] = array[j--];
        }
        i = 0;
        while(start <= end){
            array[start++] = copy[i++];
        }
        return left_count+right_count+count;


    }

    public static void main(String[] args) {
        int[] nums = {7,5,6,4};

        System.out.println(new MergSort().InversePair(nums));

    }