数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。——剑指offer

分析：一般求总数，全部可能的种树的题型基本都是用递归，回溯。
算法考察：归并排序
这道题使用一个额外空间目的是将所有数字排序成有序状态，同时分解子问题，对相邻坐标的数进行对比，记下是否逆序。之后将其排序放入下一次父问题的比较之中并且不会重复计数。

例如：1 2 1 2 1，将其分成 A 1 2 1和 B 2 1两个子问题，A的解为1并变成112，B的解为1变成12，求解子问题之后再从各自的最末端使用标记进行逐一对比。一旦A中标记比B中标记大（比如A中2比B中1大），且两者都是有序的，因此A标记下的数，大于所有后者数组标记之前的所有数（包括该标记数）。直接算出此次归并排序的逆序总数。

//test case, should return 3

public class Solution {
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1,2,1,2,1};
        System.out.println(solution.getPairs(arr));
    }
    
    public int getPairs(int [] array) {
        
        if (array.length <= 1) {
            return array.length;
        }
        
        int[] arrayCopy = new int[array.length];
        
        for (int i = 0; i < arrayCopy.length; i++) {
            arrayCopy[i] = array[i];
        }
        
        int count = getPairsCount(array,arrayCopy,0,array.length-1);
        
        return count;
    }
    
    public int getPairsCount(int[] array, int[] arraycopy,int start,int end) {
        
        if (start == end) {
            arraycopy[start] = array[start];
            return 0;
        }
        
        int mid = (end-start)/2;
//      这个递归，注意参数中两个数组的位置变化，每次都是对需要进行归并的那个数组进行处理
        int left = getPairsCount(arraycopy, array, start, start+mid);
        int right = getPairsCount(arraycopy, array, start+mid+1, end);
        
        int count = 0;
        int index = end;
        int i = start+mid;
        int j = end;
        
        while (i >= start && j >= start+mid+1) {
            if (array[i] > array[j]) {
                arraycopy[index--] = array[i--];
                count += j - (start+mid);   
            }
            
            else {
                arraycopy[index--] = array[j--];
            }
        }
        
        for(;i >= start;--i){
            arraycopy[index--] = array[i];
        }
        for(; j >= start + mid +1; --j){
            arraycopy[index--] = array[j];
        }
        
        return count+left+right;
    }
}