493. Reverse Pairs Hard

1/**
2 * [493] Reverse Pairs
3 *
4 * Given an integer array nums, return the number of reverse pairs in the array.
5 * A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [1,3,2,3,1]
10 * Output: 2
11 * Explanation: The reverse pairs are:
12 * (1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
13 * (3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1
14 * 
15 * Example 2:
16 * 
17 * Input: nums = [2,4,3,5,1]
18 * Output: 3
19 * Explanation: The reverse pairs are:
20 * (1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
21 * (2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
22 * (3, 4) --> nums[3] = 3, nums[4] = 1, 5 > 2 * 1
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	1 <= nums.length <= 5 * 10^4
28 * 	-2^31 <= nums[i] <= 2^31 - 1
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/reverse-pairs/
34// discuss: https://leetcode.com/problems/reverse-pairs/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn reverse_pairs(nums: Vec<i32>) -> i32 {
40        0
41    }
42}
43
44// submission codes end
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test_493() {
52    }
53}
54