题解 | #字符串的排列#

两种写法都能过，
简单方法就是，复制一份数组并排序，然后遍历这个有序的数组，比如第一个最小值为0，在原数组中查看0的索引，就可以得到关于0的逆序对；之后将0从原数组移除，继续遍历。
归并排序，不重复大牛的说法了，坐到0bug，一遍过就行。

import java.util.*;
public class Solution {
    int res = 0;
    public int InversePairs(int [] array) {

//             int[] sort = new int[array.length];
//             System.arraycopy(array, 0, sort,0 ,array.length);
//              Arrays.sort(sort);
//             int res = 0;
//             ArrayList<Integer> arrayList =  new ArrayList<Integer>();
//             for (int i : array) {
//                 arrayList.add(i);
//             }


//             for(int i =0;i<sort.length;i++){
//                 int index = arrayList.indexOf(sort[i]);

//                 res += index;
//                 res = res%1000000007;
//                 arrayList.remove(index);
//             }
//             return res%1000000007;
        sort(array,0,array.length-1);
        return res;
    }
    public void sort(int [] array, int l, int r) {
        if(array.length == 0 || l == r){
            return;
        }
        int mid = l + (r-l)/2;
        sort(array, l, mid);
        sort(array, mid+1, r);
        merge(array, l, mid, r);
    }
    public void merge(int [] array,int l, int mid, int r) {
        int i = l;
        int j =mid+1;
        int t =0;
        int[] temp = new int[r-l+1];
        while(i<=mid && j<= r){
            if(array[i] <= array[j]){
                temp[t++] = array[i++];
            }else{
                res += (mid-i+1);
                res = res% 1000000007;
                temp[t++] = array[j++];
            }
        }
        while(i<=mid){
             temp[t++] = array[i++];
        }
        while(j<=r){
             temp[t++] = array[j++];
        }
        System.arraycopy(temp,0, array,l, temp.length);
    }
}