493. Reverse Pairs (Hard)

https://leetcode.com/problems/reverse-pairs/

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.

Solutions

class Solution {

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + ((right - left) >> 1);
        return mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right) + merge(nums, left, mid, right);
    }

    private int merge(int[] nums, int left, int mid, int right) {
        int[] helper = new int[right - left + 1];

        int i = 0, rst = 0;
        int p1 = left, p2 = mid + 1, p = mid + 1;
        while (p1 <= mid) {
            while (p <= right && nums[p1] / 2.0 > nums[p]) {
                p++;
            }

            rst += p - (mid + 1);

            while (p2 <= right && nums[p1] > nums[p2]) {
                helper[i++] = nums[p2++];
            }

            helper[i++] = nums[p1++];
        }
        while (p2 <= right) {
            helper[i++] = nums[p2++];
        }

        for (i = 0; i < helper.length; i++) {
            nums[left + i] = helper[i];
        }
        return rst;
    }
}

Incorrect Solutions

References

https://blog.csdn.net/magicbean2/article/details/78717238

http://www.mamicode.com/info-detail-2537761.html

https://github.com/cherryljr/LeetCode/blob/master/Reverse%20Pairs.java

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""