推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

public class Solution {
   
    public int InversePairs(int [] array) {
   
        
    }
}

思路：

归并排序，分而治之。

将数组分成左右两组并各自排序，left[]，right[]；

然后将两个数组的值依次比较；

如果 left[i] 大于 right[j]，那么left[i]之后的都大于right[i]。

实现：

public class Solution {
   
    //逆序对的个数
    int cnt;

    public int InversePairs(int[] array) {
   
        if (array.length != 0) {
   
            divide(array, 0, array.length - 1);
        }
        return cnt;
    }


    public void divide(int[] arr, int start, int end) {
   
        if (start >= end) {
   
            return;
        }
        int mid = (start + end) / 2;
        divide(arr, start, mid);
        divide(arr, mid + 1, end);

        merge(arr, start, mid, end);
    }


    private void merge(int[] arr, int start, int mid, int end) {
   
        int[] temp = new int[end - start + 1];

        //存一下变量
        int i = start;
        int j = mid + 1;
        int k = 0;

        //开始两两比较，若前面的数大于后面的数，就构成逆序对
        while (i <= mid && j <= end) {
   
            //r如果前面的小于后面的，不构成逆序对，则直接存进去，并移动前面数所在数组的指针
            if (arr[i] <= arr[j]) {
   
                temp[k++] = arr[i++];
            } else {
   
                temp[k++] = arr[j++];
                //a[i] > [j] 了，那么这一次，从a[i]开始到a[mid]必定哦都是大于这个a[j]的，因为此时分治的两边已经是各自有序了
                cnt = (cnt + mid - i + 1) % 1000000007;
            }
        }

        while (i <= mid) {
   
            temp[k++] = arr[i++];
        }
        while (j <= end) {
   
            temp[k++] = arr[j++];
        }
        //将临时数组数组中的复制到数组中去
        for (k = 0; k < temp.length; k++) {
   
            arr[start + k] = temp[k];
        }

    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！