493 Reverse Pairs

Search…

493 Reverse Pairs

493. Reverse Pairs​
1. Question
Given an arraynums, we call(i, j)an important reverse pair ifi < jandnums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example1:
1
Input: [1,3,2,3,1]
2
​
3
Output: 2
Copied!
Example2:
1
Input: [2,4,3,5,1]
2
​
3
Output: 3
Copied!
Note:
1.The length of the given array will not exceed50,000.
2.All the numbers in the input array are in the range of 32-bit integer.
2. Implementation
(1) Merge Sort
1
class Solution {
2
    public int reversePairs(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6
​
7
        int n = nums.length;
8
        int[] res = new int[1];
9
        mergeSort(nums, 0, n - 1, res);
10
        return res[0];
11
    }
12
​
13
    public void mergeSort(int[] nums, int start, int end, int[] res) {
14
        if (start >= end) {
15
            return;
16
        }
17
​
18
        int mid = start + (end - start) / 2;
19
        mergeSort(nums, start, mid, res);
20
        mergeSort(nums, mid + 1, end, res);
21
​
22
        int count = 0;
23
        int left = start, right = mid + 1;
24
​
25
        while (left <= mid) {
26
            if (right <= end && (nums[left] > 2 * (long)nums[right])) {
27
                ++count;
28
                ++right;
29
            }
30
            else {
31
                res[0] += count;
32
                ++left;
33
            }
34
        }
35
        merge(nums, start, mid, end);
36
    }
37
​
38
    public void merge(int[] nums, int start, int mid, int end) {
39
        int[] temp = new int[end - start + 1];
40
​
41
        int i = start;
42
        int j = mid + 1;
43
        int k = 0;
44
​
45
        while (i <= mid && j <= end) {
46
            if (nums[i] < nums[j]) {
47
                temp[k++] = nums[i++];
48
            }
49
            else {
50
                temp[k++] = nums[j++];
51
            }
52
        }
53
​
54
        while (i <= mid) {
55
            temp[k++] = nums[i++];
56
        }
57
​
58
        while (j <= end) {
59
            temp[k++] = nums[j++];
60
        }
61
​
62
        for (int m = start; m <= end; m++) {
63
            nums[m] = temp[m - start];
64
        }
65
    }
66
}
Copied!
3. Time & Space Complexity
Merge Sort:时间复杂度O(nlogn), 空间复杂度O(n)

462 Minimum Moves to Equal Array Elements II

Binary Search

Last modified 2yr ago

Copy link

Contents

493. Reverse Pairs

1. Question

2. Implementation

3. Time & Space Complexity

493. Reverse Pairs​

1. Question

2. Implementation

3. Time & Space Complexity

493. Reverse Pairs