brezezee

逆序对

• 归并思想

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if (!size(nums)) return 0;
        int cnt = 0;
        int data[size(nums)];
        for (int i = 0; i < nums.size(); ++ i) data[i] = nums[i];
        
        int tmp[size(nums)];
        function<void(int, int)> merge = [&](int l, int r) {
            if (l == r) return ;
            int mid = l + r >> 1;
            
            merge(l, mid), merge(mid + 1, r);
            int i = l, j = mid + 1, k = 0;
            while (i <= mid && j <= r){
                if (data[i] <= data[j]) tmp[k++] = data[i++];
                else {
                    tmp[k++] = data[j++];
                    // data[j] < data[i]时，说明[i, mid]范围内的数都大于data[j]
                    cnt += mid + 1 - i;  
                }
            }
            while (i <= mid) tmp[k++] = data[i++];
            while (j <= r) tmp[k++] = data[j++];
            for (int i = l, k = 0; i <= r; ++ i, ++ k) data[i] = tmp[k];
            
        };
        merge(0, nums.size()-1);
        return cnt;
    }
};