题解 | #数组中的逆序对#

1.使用字典树，前缀树

struct Trie
{
    int sum = 0;
    vector<Trie*> child = {nullptr,nullptr};
    Trie() = default;
};


class Solution {
public:
    void add(int num)
    {
        Trie* curr = root;
        for(int k = Highsize;k>=0;--k)
        {
            int bit = (num >> k) &1;
            if(curr->child[bit] == nullptr)
                curr->child[bit] = new Trie();
            curr = curr->child[bit];
            curr->sum++;    
        }
    }
    int getSum(int num)
    {
        Trie* curr = root;
        int result = 0;
        for(int k = Highsize;k>=0;--k)
        {
            int m = (num >> k) &1;
            if(m == 1)
            {
                if(curr->child[m] == nullptr)
                    return result;
                curr = curr->child[m];
            }
            else
            {
                if(curr->child[1] != nullptr)
                    result += curr->child[1]->sum;
                if(curr->child[0] == nullptr)
                    return result;
                curr = curr->child[0];
            }
        }
        result += curr->sum;
        return result;
    }
    int InversePairs(vector<int> data) {
        int mod = 1000000007;
        root = new Trie();
        long sum = 0;
        for(int i = 1;i<data.size();++i)
        {
            add(data[i-1]);
            sum += getSum(data[i]);
        }
        return sum % mod;
    }
private:
    Trie* root;
    const int Highsize = 29;
};

2.使用归并排序，并在排序时统计逆数对

class Solution {
public:
    int merge(vector<int> &num,int low,int mid,int high)
    {
        int mod = 1000000007;
        vector<int> temp(high-low+1,0);
        int i = low,j = mid + 1;
        int k = 0;
        int sum =0;
        while(i <= mid && j <= high)
        {
            //如果左数组的元素小于右数组，则不能构成逆序对
            if(num[i] <= num[j])
            {
                temp[k++] = num[i++];
            }
            else
            {
            //如果左数组的元素大于右数组的，因为左数组是升序排列好的，那么左数组当前元素以及之后的元素都会与右数组的当前元素构成逆序
                temp[k++] = num[j++];
                sum = (sum + (mid-i+1)) % mod;
            }
        }
        while(i<=mid)
        {
            temp[k++] = num[i++];
        }
        while(j<=high)
        {
            temp[k++] = num[j++];
        }
        for(int r = low;r <= high;r++)
        {
            num[r] = temp[r-low];
        }
        return sum % mod;
    }
    int mergesort(vector<int> &num,int low,int high)
    {   
        static int res = 0;
        int mod = 1000000007;
        if(low < high)
        {
            int mid = (low + high)/2;
            mergesort(num, low, mid);
            mergesort(num, mid+1, high);
            res += merge(num, low, mid, high);
        }
        return res % mod;
    }
    int InversePairs(vector<int> data) {
        //使用归并排序
        int low = 0;
        int high = data.size()-1;
        return mergesort(data, low, high);
    }
};