Fork me on GitHub

493.翻转对

发表于 | 分类于 ， | 次阅读
字数统计: 1k | 阅读时长 ≈ 4

解法1：树状数组+二分查找

基本思路

题目要找的是前面的数比后面的数的两倍大的数，那么我们可以从后向前遍历，将以前遍历过的数存起来，得到序列$sum$，然后在遍历过的数中找到比当前数的1/2倍小的数的个数，这样最终就可以得到解。

难点1：如何计算个数？

一开始想到的肯定是前缀和了，第$i$个前缀和表示小于等于第$i$个数的总个数，我们在序列$sum$中找到比当前数的1/2倍小的最大的数的下标$i$，然后求第$i$个前缀和就可以了。但是有个问题：前缀和的更新不方便。

这道题涉及到若干次查找和更新，所以我们可以考虑用树状数组来存遍历过的数的个数。所以我们定义树状数组$sum$来求前缀和，函数$getSum(i)$就可以求出第$i$个前缀和了。

难点2：如何找到比当前数的1/2倍小的最大的数的下标？

首先，我们将原序列从小到大排序得到序列$v$，然后用二分查找来找到比当前数的1/2倍小的最大的数的下标，且下标从1开始，这样做的原因是树状数组的下标是从1开始的，所以这样可以对应，然后求和。

难点3：如何更新树状数组？

首先更新树状数组需要知道第$i$个数是哪个数。由于第$i$个前缀和表示小于等于第$i$个数的个数，所以，我们需要用$map$来将拍好序的数字的位置确定下来，$map[j] = i$表示数字$j$是第$i$个数，这样，值小的数字的位置小，而且$map$中存的位置是这个数的最大位置，因为二分查找的时候找到的也是相同值的最大位置，这样可以对应。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    void update(vector<int> &sum , int val , int index){
        while(index < sum.size()){
            sum[index] += val;       //每次存入都是要+1
            index += (index & -index);
        }
    }
    int getSum(vector<int> &sum , int index){
        int res = 0;
        while(index > 0){
            res += sum[index];
            index -= (index & -index);
        }
        return res;
    }
    int left_bound(const vector<int> &v , double target){
        int l = 0 , r = v.size();
        while(l < r){
            int mid = (l + r) / 2;
            if(v[mid] < target){
                l = mid + 1;
            }
            else r = mid;
        }
        return l;
    }
    
    int reversePairs(vector<int>& nums) {
        vector<int> v(nums);
        sort(v.begin() , v.end());
        int n = nums.size();
        vector<int> sum(n+1 , 0);     // 树状数组
        map<int , int> m;
        for(int i = 0 ; i<n ; ++i){
            m[v[i]] = i + 1;
        }
        int res = 0;
        for(int i = n-1 ; i>=0 ; --i){
            int index = left_bound(v , nums[i] / 2.0);
            res += getSum(sum , index);
            update(sum , 1 , m[nums[i]]);
        }
        return res;
    }
    
};

解法2：归并排序

基本思路

在归并排序中，我们先把序列分成小块，然后逐块合并排序，在本题中，相邻两块除了要排序以外，我们需要计算前一块中的数$nums[i]$和后一块中的$num[j]$可以形成多少个翻转对。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    void merge(vector<int> &nums , int l , int mid , int r){ //将两块排序后合并
        vector<int> L(nums.begin()+l , nums.begin()+mid+1);
        vector<int> R(nums.begin()+mid+1 , nums.begin()+r+1);
        int i = 0 , j = 0;
        int n1 = mid - l + 1;
        int n2 = r - mid;
        for (int k = l; k <= r; k++) {
            if (j >= n2 || (i < n1 && L[i] < R[j]))
                nums[k] = L[i++];
            else
                nums[k] = R[j++];
        }

    }
    int mergeSort(vector<int> & nums , int l , int r){
        if(l < r){
            int mid = (l + r) / 2;
            int res = mergeSort(nums , l , mid) + mergeSort(nums , mid + 1 , r);
            int j = mid + 1;
            for(int i = l ; i<=mid ; ++i){ // 相邻两块求翻转对
                for(j ; j<=r ; ++j){
                    if(nums[i] <= nums[j] * 2LL){
                        break;
                    }
                }
                res += (j - mid - 1);
            }
            merge(nums , l , mid , r);
            return res;
        }
        else return 0;   //当l == r时，即每块不可再分了
    }
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums , 0 , nums.size() - 1);
    }
};