leetcode493. Reverse Pairs

    public int reversePairs(int[] nums) {
        if (nums == null) {
            return 0;
        }
        long[] numsInLong = Arrays.stream(nums).asLongStream().toArray();
        return reversePairs(numsInLong, 0, nums.length-1);
    }

    public int reversePairs(long[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        int leftReversePairs = reversePairs(nums, left, mid);
        int rightReversePairs = reversePairs(nums, mid+1, right);
        int count = 0;
        int cur = mid;
        while(cur >= left) {
            int index =  findRightMostIndex(nums, nums[cur], mid+1, right);
            int tmpCount = index - mid - 1;
            if (tmpCount == 0) {
                break;
            }
            count += tmpCount;
            cur--;
        }

        mergeSort(nums, left, right);
        return count + leftReversePairs + rightReversePairs;
    }

    public void mergeSort(long[] nums, int left, int right) {
        long[] copy = Arrays.copyOfRange(nums, left, right+1);
        int mid = (left + right) / 2 - left;
        int leftIndex = 0;
        int rightIndex = mid + 1;
        int index = left;
        while (index <= right) {
            if (rightIndex > right - left) {
                nums[index++] = copy[leftIndex++];
            } else if (leftIndex > mid) {
                nums[index++] = copy[rightIndex++];
            } else if (copy[leftIndex] <= copy[rightIndex]) {
                nums[index++] = copy[leftIndex++];
            } else {
                nums[index++] = copy[rightIndex++];
            }
        }
    }
    public int findRightMostIndex(long[] nums, long num, int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (num > nums[mid] * 2) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }