reverse-pairs.md

493. 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

• 给定数组的长度不会超过50000。
• 输入数组中的所有数字都在32位整数的表示范围内。

题解：

impl Solution {
    pub fn reverse_pairs(mut nums: Vec<i32>) -> i32 {
        let n = nums.len() - 1;

        Self::merge_sort(&mut nums, 0, n)
    }

    fn merge_sort(nums: &mut [i32], left: usize, right: usize) -> i32 {
        if left >= right {
            return 0;
        }

        let mid = (left + right) / 2;
        let mut total = Self::merge_sort(nums, left, mid) + Self::merge_sort(nums, mid + 1, right);

        let mut p = left;
        let mut q = mid + 1;

        while p <= mid && q <= right {
            if nums[p] as i64 > (nums[q] as i64) * 2 {
                total += (mid - p + 1) as i32;
                q += 1;
            } else {
                p += 1;
            }
        }

        let mut i = left;
        let mut j = mid + 1;
        let mut tmp = vec![];

        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp.push(nums[i]);
                i += 1;
            } else {
                tmp.push(nums[j]);
                j += 1;
            }
        }

        while i <= mid {
            tmp.push(nums[i]);
            i += 1;
        }

        while j <= right {
            tmp.push(nums[j]);
            j += 1;
        }

        for k in left..=right {
            nums[k] = tmp[k - left];
        }

        return total;
    }
}