剑指Offer-数组中的逆序对

迷南。 2022-02-19 03:15 163阅读 0赞

## 题目描述 ##

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

###### 输入描述: ######

题目保证输入的数组中没有的相同的数字

> 数据范围：  
> 对于%50的数据,size<=104  
> 对于%75的数据,size<=105  
> 对于%100的数据,size<=2\*105

###### 示例1 ######

输入 1,2,3,4,5,6,7,0  
输出 7

解题思路—**暴力解题法**：双循环判断数组值大小，在牛客网上无法ac，程序未能在规定时间内运行结束。**十分不推荐！**  
解题思路—**归并排序**：这道题是典型的使用归并排序思想的题目，**使用归并排序，时间复杂度为O(*nlog(n)*)，空间复杂度O(*n*)**。归并排序就是**不停地把数据分成前后两个数组，直到递归分到每个数组仅有一个数据项为止**。然后依次开始比较数字大小，从相邻数字比较到跨组数字比较，与双循环相比，时间复杂度大大减小！**要注意的是：从下而上的数组都是有序的。** 要充分理解递归排序的思想，才能看懂代码，特别是 `count += middle-i+1`这一步，一定要知道**前后两个数组已经是有序的**。（不能理解归并排序的可以找个排序动画，推荐五分钟学算法，结合思考，更易理解！）

## Java解题—归并排序 ##

public class Solution {
        public int count = 0;
        public int InversePairs(int [] array) {
            if (array.length == 0)
                return 0;
            mergeSort(array, 0, array.length-1);
            return count;
        }
        
        //归并排序的分治---分
        public void mergeSort(int[] array, int left, int right){
            if(left>=right)
                 return;
    
            int mid = (left+right)/2;
            //递归分
            mergeSort(array, left, mid);
            mergeSort(array, mid+1, right);
            // 治
            Sort(array, left, mid, right);
        }
    
        public void Sort(int[] array, int left, int middle, int right){
            int[] temp = new int[right-left+1];
            int i = left, j = middle+1, index = 0;
            // 开始两两进行比较，若前面的数大于后面的数，构成逆序对
            while(i<=middle && j<=right){
                if(array[i]>array[j]){
                    temp[index++] = array[j++];
                    count += middle-i+1;
                    count = count>1000000007?count%1000000007:count;
                }
                else
                    temp[index++] = array[i++];
            }
            while(i<=middle) temp[index++] = array[i++];
            while(j<=right) temp[index++] = array[j++];
            // 覆盖原数组
            for(int k=0;k<temp.length;k++)
                array[left+k]=temp[k];
        }
    }