leetcode-go/leetcode/hard/493.reverse-pairs.java

class Solution {
    private int[] aux;

    public int reversePairs(int[] nums) {
        aux = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int beg, int end) {
        int res = 0;
        if (end <= beg) return res;
        int mid = beg + (end - beg) / 2;
        res += mergeSort(nums, beg, mid);
        res += mergeSort(nums, mid + 1, end);
        for (int i = beg, j = mid + 1; i <= mid; i++) {
            for (; j <= end && 2L * nums[j] < (long) nums[i]; j++);
            res += j - (mid + 1);
        }
        for (int i = beg, j = mid + 1, k = beg; k <= end; k++) {
            if (i == mid + 1) {
                aux[k] = nums[j++];
            } else if (j == end + 1) {
                aux[k] = nums[i++];
            } else {
                if (nums[i] < nums[j]) aux[k] = nums[i++];
                else aux[k] = nums[j++];
            }
        }
        System.arraycopy(aux, beg, nums, beg, end - beg + 1);
        return res;
    }
}