762.Number Stream to Intervals#

1
Given a list of integers nums,
2

3
return the number of pairs i < j such that nums[i] > nums[j] * 3.
4

5
Constraints
6

7
n ≤ 100,000 where n is the length of nums
8
Example 1
9
Input
10
nums = [7, 1, 2]
11
Output
12
2
13
Explanation
14
We have the pairs (7, 1) and (7, 2)

1
class Solution {
2
public:
3
    void merge(vector<int> &nums, int i, int mid, int j)
4
    {
5

6
        vector<int> ans(j - i + 1);
7
        int l = i, r = mid + 1;
8
        int cnt = 0;
9

10
        while(l <= mid && r <= j)
11
        {
12
            if(nums[l] <= nums[r])
13
            {
14
                ans[cnt] = nums[l];
15
                l++;
16
            }
17
            else
18
            {
19
                ans[cnt] = nums[r];
20
                r++;
21
            }
22
            cnt++;
23
        }
24

25
        while(l <= mid) ans[cnt++] = nums[l++];
26
        while(r <= j) ans[cnt++] = nums[r++];
27

28
        cnt = 0;
29
        while(i <= j) nums[i++] = ans[cnt++];
30
    }
31

32
    int mergeSort(vector<int> &nums, int l, int r)
33
    {
34
        if(r <= l) return 0;
35
        int ans = 0;
36
        int mid = (l + r) / 2;
37
        ans += mergeSort(nums, l, mid);
38
        ans += mergeSort(nums, mid + 1, r);
39

40
        int p = l;
41
        int q = mid + 1;
42
        while(p <= mid && q <= r)
43
        {
44
            if(nums[p] > nums[q] * 3)
45
            {
46
                ans += (mid - p + 1);
47
                q++;
48
            }
49
            else p++;
50
        }
51
        merge(nums, l, mid, r);
52
        return ans;
53
    }
54

55
    int solve(vector<int> &nums)
56
    {
57
        int ans = mergeSort(nums, 0, nums.size() - 1);
58
        return ans;
59
    }
60
};