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

import java.util.*;
// 既然逆序了，应该从后往前遍历，对于遍历的数，只关心曾经遍历的数有多少比我小，则有多少逆序对，
// 对已经遍历的数的查找希望能快一点，这里空间换时间，遍历一个数便通过插入排序放到他该去的地方，
// tail 数组是从大到小排的，查找时二分
public class Solution {
    static int mod = (int)1.0e9+7;
    public int InversePairs(int [] array) {
        int n = array.length, end = 0, total = 0;
        int tail[] = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int val = insert(tail, end, array[i]);
            total += val;
            total %= mod;
            end++;
        }
        return total;
    }

    public int insert(int[] nums, int end, int val) {
        int l = 0, r = end;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < val) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        for (int i = end; i > l; i--) {
            nums[i] = nums[i - 1];
        }
        nums[l] = val;
        return l - 0;
    }
}