逆序问题及其几种解法

设(A)为一个有(n)个数字的序列，其中所有的数字各不相同。如果存在正整数(i)和(j)，使得(1 le i lt j le n)且(A[i] gt A[j])，那么数对((A[i], A[j]))就被称为(A)的一个逆序对，也称作逆序，逆序对的数量就是逆序数。如下图所示，((A[2], A[4]))就是一个逆序对。

LeetCode 面试题51. 数组中的逆序对

分治法

假设我们要统计数列(A)中逆序对的个数。如图所示，我们可以将数列(A)分成两半得到数列B和数列C。因此，数列A中所有的逆序对必属于下面三者其一：
(1). (i,j)都属于数列(B)的逆序对
(2). (i,j)都属于数列(C)的逆序对
(3). (i)属于数列(B)而(j)属于数列(C)的逆序对

所以，我们只需要分别统计这三种逆序对，然后再加起来就行了。(1)和(2)可以通过递归求得，对于(3)，我们可以对数列(C)中的每个数字，统计在数列(B)中比它大的数字的个数，再把结果加起来即可。因为每次分治时数列的长度都会减半，所以递归的深度是(O(log n))，而每一层有(O(n))个操作，因此算法的时间复杂度为(O(nlog n))。

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        auto mid = nums.begin() + n / 2;
        vector<int> left(nums.begin(), mid);
        vector<int> right(mid, nums.end());
        
        int cnt = 0;
        
        cnt += reversePairs(left);
        cnt += reversePairs(right);
        
        int nums_idx = 0;
        int left_idx = 0;
        int right_idx = 0;
        
        while (nums_idx < n) {
            if (left_idx < left.size() && (right_idx == right.size() || left[left_idx] <= right[right_idx])) {
                nums[nums_idx++] = left[left_idx++];
            } else {
                cnt += n / 2 - left_idx;
                nums[nums_idx++] = right[right_idx++];
            }
        }
        return cnt;
    }
};

树状数组

我们构建一个值的范围是(1sim n)的树状数组，按照(j=0,1,2,cdots,n-1)进行如下操作：

(j- ext{sum}(A[j]))
( ext{add}(A[j], 1))

对于每个(j)，树状数组查询得到的前(A[j])项的和就是满足(i lt j, A[i] le A[j])的(i)的个数。因此，把这个值从(j)中减去，得到的就是满足(i lt j, A[i] gt A[j])的(i)的个数。由于对每个(j)的复杂度是(O(log n))，所以整个算法的复杂度是(O(nlog n))。注意到树状数组的范围是(1sim n)，而原始序列中可能包含负数或者非常大的数，因此我们需要对原始数据进行一次映射（离散化），把原始数据映射到(1sim n)区间上。

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        
        if (nums.size() <= 1) return 0;
        
        vector<int> nums_copy(nums.begin(), nums.end());
        sort(nums_copy.begin(), nums_copy.end());
        
        unordered_map<int, int> num_val_map;
        n = 1;

        // 离散化
        for_each (nums_copy.begin(), nums_copy.end(), [&num_val_map, this](const int val) {
            if (num_val_map[val] == 0) num_val_map[val] = n++;
        });
        
        bits.resize(n);
        fill(bits.begin(), bits.end(), 0);
        int ans = 0;
        for(int i = 0;i < nums.size(); ++i) {
            ans += i - sum(num_val_map[nums[i]]);
            add(num_val_map[nums[i]], 1);
        }
        return ans;
    }
private:
    int n;
    vector<int> bits;
    
    inline int lowbit (int x) {
        return x & (-x);
    }
    
    void add (int idx, int val) {
        while (idx < n) {
            bits[idx] += val;
            idx += lowbit(idx);
        }
    }
    
    int sum (int idx) {
        int res = 0;
        while (idx > 0) {
            res += bits[idx];
            idx -= lowbit(idx);
        }
        return res;
    }
};

LeetCode 315. 计算右侧小于当前元素的个数

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<Pair> num_pairs(nums.size());
        vector<int> counts(nums.size(), 0);
        for (int i = 0;i < nums.size();++i) {
            num_pairs[i].first = nums[i];
            num_pairs[i].second = i;
        }
        reversePairs(num_pairs, counts);
        return counts;
    }
private:
    using Pair = pair<int, int>;
    void reversePairs(vector<Pair>& nums, vector<int>& counts) {
        int n = nums.size();
        if (n <= 1) return;
        auto mid = nums.begin() + n / 2;
        vector<Pair> left(nums.begin(), mid);
        vector<Pair> right(mid, nums.end());
        
        reversePairs(left, counts);
        reversePairs(right, counts);
        
        int nums_idx = 0;
        int left_idx = 0;
        int right_idx = 0;
        
        while (nums_idx < n) {
            if (left_idx < left.size() && (right_idx == right.size() || left[left_idx].first <= right[right_idx].first)) {
                nums[nums_idx++] = left[left_idx++];
            } else {
                for (int i = left_idx; i < n/2; i++) {
                    counts[left[i].second] += 1;
                };
                nums[nums_idx++] = right[right_idx++];
            }
        }
    }
};