Sword to Offer-51 数组中的逆序对 ❀❀

07 May 2020 in Algorithm

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

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

解题思路：

（在数据量较大情况下，用类似冒泡排序的双重循环进行逆序对判断会超时，笑~）

所以只能考虑时间复杂度更低的排序算法，如归并排序：
1、采用递归方法进行子序列的划分和归并；
2、归并时，位于前面的子数组arr[i~mid]元素有序，若arr[i]>arr[j]（位于后面的子数组的第一个元素），那么它后面的元素也都>arr[j]，即arr[i~mid]元素都与arr[j]元素组成逆序对，其个数为(mid -i +1)，统计整个排序过程中的这个值的总和即为原数组所有逆序对数。

问题图解：

AC代码：

// Reversed Pairs of Numbers in Array （Merge Sort）

public class Solution {
    
    private long count = 0;
    private int[] tmpArr;
    
    public int InversePairs(int [] array) {
        if (array==null || array.length==0) {
            return 0;
        }
        tmpArr = new int[array.length];  // 初始化临时数组
        divide(array, 0, array.length-1);
        return (int)(count%1000000007);
    }
    
    private void divide(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        // 递归划分
        divide(arr, low, mid);
        divide(arr, mid + 1, high);
        // 归并排序
        mergeSort(arr, low, mid, high);
    }
    
    private void mergeSort(int[] arr, int low, int mid, int high) {
        int i = low, j = mid + 1, k = low;
        while (i<=mid && j<=high) {
            if (arr[i] <= arr[j]) {
                tmpArr[k++] = arr[i++];
            }
            else {
                tmpArr[k++] = arr[j++];
                count += mid-i+1;
            }
        }
        while (i <= mid) {
            tmpArr[k++] = arr[i++];
        }
        while (j <= high) {
            tmpArr[k++] = arr[j++];
        }
        //  排序完一小部分就拷贝回原数组
        for (k=low; k<=high; k++) {
            arr[k] = tmpArr[k];
        }
    }
}

补充说明：

• 注意：
  1、此处用long类型变量count来记录逆序对数目，用int只AC50%，要求的返回类型count%1000000007为int类型，求余后类型转换为int即可；

  2、归并排序的归并完成时，需要将排好的tmp数组中的值拷贝回原数组对应位置，原因是为了保证下一次归并过程中，原数组中待合并的两个子数组依旧有序。

• 这里是牛客编码链接