题解 | #数组中的逆序对#

保证前面的数组有序，使用二分法查找插入的位置，即可计算能和前面的数组成多少逆序对。 二分插入排序比较好懂。

| 1 | 2 | 3 | null | 5 | 6 | 7 | 8 | 4 |

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        int[] arr = new int[]{7,6,5,4,3,2,1,0};
        int result = new Solution().InversePairs(arr);
        System.out.println(result);
    }

    public int InversePairs(int[] array) {

        long result = 0;

        for (int j = 1; j < array.length; j++) {

            int tmp = array[j];
            int index = Arrays.binarySearch(array, 0, j, tmp);
            int pos = (-index - 1);

            if (pos < j) {
                int len = j - pos;
                System.arraycopy(array, pos, array, pos+1, len);
                array[pos] = tmp;
                result += len;
                result %= 1000000007;
            }
        }

        return (int) result;
    }
}