Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/493.html

493. Reverse Pairs

Level

Hard

Description

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.

Example 1:

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

Output: 2

Example 2:

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.

Solution

Use the idea of merge sort. In merge sort, the original array is split into two parts, each of which is sorted, and then merged. Suppose the two parts have already been sorted. Before merging the two parts, if there exists an index i in the left part and an index j in the right part such that nums[i] > 2 * nums[j], then all indices from i to the end of the left part have numbers greater than 2 * nums[j], so increase the count accordingly.

  • class Solution {
    public int reversePairs(int[] nums) {
        return mergeSortAndCount(nums, 0, nums.length - 1);
    }

    public int mergeSortAndCount(int[] nums, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int midIndex = (endIndex - startIndex) / 2 + startIndex;
            int count = mergeSortAndCount(nums, startIndex, midIndex) + mergeSortAndCount(nums, midIndex + 1, endIndex);
            int index1 = startIndex, index2 = midIndex + 1;
            while (index1 <= midIndex && index2 <= endIndex) {
                if ((long) nums[index1] > 2 * (long) nums[index2]) {
                    count += midIndex - index1 + 1;
                    index2++;
                } else
                    index1++;
            }
            merge(nums, startIndex, midIndex, endIndex);
            return count;
        } else
            return 0;
    }

    public void merge(int[] nums, int startIndex, int midIndex, int endIndex) {
        int length = endIndex - startIndex + 1;
        int[] newArray = new int[length];
        int index1 = startIndex, index2 = midIndex + 1;
        int index = 0;
        while (index1 <= midIndex && index2 <= endIndex) {
            if (nums[index1] <= nums[index2])
                newArray[index++] = nums[index1++];
            else
                newArray[index++] = nums[index2++];
        }
        while (index1 <= midIndex)
            newArray[index++] = nums[index1++];
        while (index2 <= endIndex)
            newArray[index++] = nums[index2++];
        for (int i = 0; i < length; i++)
            nums[startIndex + i] = newArray[i];
    }
}

  • // OJ: https://leetcode.com/problems/reverse-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
    vector<int> tmp;
    int ans = 0;
    void solve(vector<int> &A, int begin, int end) {
        if (begin + 1 >= end) return;
        int mid = (begin + end) / 2, i = begin, j = mid, k = begin, t = mid;
        solve(A, begin, mid);
        solve(A, mid, end);
        for (; i < mid; ++i) {
            while (j < end && A[j] < A[i]) {
                tmp[k++] = A[j++];
            }
            while (t < end && (long)A[t] * 2 < A[i]) ++t;
            ans += t - mid;
            tmp[k++] = A[i];
        }
        for (; j < end; ++j) tmp[k++] = A[j];
        for (int i = begin; i < end; ++i) A[i] = tmp[i];
    }
public:
    int reversePairs(vector<int>& A) {
        tmp.assign(A.size(), 0);
        solve(A, 0, A.size());
        return ans;
    }
};

  • class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        s = set()
        for num in nums:
            s.add(num)
            s.add(num * 2)
        alls = sorted(s)
        m = {v: i for i, v in enumerate(alls, 1)}
        ans = 0
        tree = BinaryIndexedTree(len(m))
        for num in nums[::-1]:
            ans += tree.query(m[num] - 1)
            tree.update(m[num * 2], 1)
        return ans

############

import bisect


class Solution(object):
  def reversePairs(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    ans = 0
    bst = []
    for num in nums:
      right = 2 * num
      idx = bisect.bisect_right(bst, right)
      ans += len(bst) - idx
      bisect.insort(bst, num)
    return ans


  • type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func reversePairs(nums []int) int {
	s := make(map[int]bool)
	for _, num := range nums {
		s[num] = true
		s[num*2] = true
	}
	var alls []int
	for num := range s {
		alls = append(alls, num)
	}
	sort.Ints(alls)
	m := make(map[int]int)
	for i, num := range alls {
		m[num] = i + 1
	}
	tree := newBinaryIndexedTree(len(m))
	ans := 0
	for i := len(nums) - 1; i >= 0; i-- {
		ans += tree.query(m[nums[i]] - 1)
		tree.update(m[nums[i]*2], 1)
	}
	return ans
}

All Problems

All Solutions