转载

逆序对

逆序对

题目

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

思想

归并排序

以书上{7, 5, 6 , 4} 为例

  • 分解和归并过程

这里写图片描述

  • 分解过程不多说,跟归并排序一样,合并过程有点不同

    这里写图片描述

    其两个指针开始是指向两边最大元素,如果p1 > p2,那么相应的就有 p2 - low + 1(右数组中最小元素位置)个逆序对, 比如 7 大于 6, 那么就有两个逆序对{7, 6},{7, 4}, 再把7赋值进copy数组(跟归并排序一样的辅助数组), 如果 p1 <= p2, 只是简单地将p2复制到辅助数组,因为此时没有逆序对。

    注意不论是P1、P2还是P3,都是从末端向前端移动

代码

public class Solution {
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0) return 0;
        int start = 0; int end = array.length-1;
        int []copy = new int[array.length];
         return digui(array, copy, start, end);
    }
    public int digui(int []array, int [] copy, int start, int end) {
        //partition
        if(start >= end) return 0;
        
        int middle = (start + end) / 2;
        
        int left = digui(array, copy, start, middle);
        
        int right = digui(array, copy, middle+1, end);
        
        int result = 0;
        
        int indexA = middle; int indexB = end; int k = end;
        while(indexA >= start && indexB >= middle+1) {
            if(array[indexA] > array[indexB]) {
                copy[k--] = array[indexA]; indexA--; 
                result += indexB-middle;
                if(result > 1000000007) result = result % 1000000007;
            }else{
                copy[k--] = array[indexB]; indexB--;
            }
        }
        while(indexA >= start) {copy[k--] = array[indexA]; indexA--;}
        while(indexB >= middle+1) {copy[k--] = array[indexB]; indexB--;}
        
        k = start;
        for(int i = start; i <= end; i++) {
            array[i] = copy[k++];
        }
        return (left + right + result) % 1000000007;
    }
}
正文到此结束
本文目录