315. Count of Smaller Numbers After Self.md

315. Count of Smaller Numbers After Self

思路

给定一个数组，计算每个数字右边所有小于这个数字的个数。

思路一、BST

我们从后往前遍历数组，如果某个数字的右边所有数字都是有序的，那么我们就可以使用二分计算该数字右边所有小于这个数字的个数，但是如何维护有序呢，如果使用插入排序，那每次维护有序数组的时间复杂度为O(n)，所以总的复杂度为O(n^2)，这和暴力法是一样的。

除了有序数组之外，二叉搜索树也可以进行二分。而每次向二叉树里插入元素的复杂度平均为O(logn)，所以总的时间复杂度平均就为O(nlogn)。另外，每个节点需要存放以这个节点为根的树有多少个节点。

时间复杂度平均为O(nlogn)，空间复杂度为O(n)。注意BST可能会退化成链表，这样时间复杂度就为O(n^2)了。

思路二、归并排序

如果某个元素nums[i]大于其右边的某个元素nums[j]（j > i），那么这元素<i, j>就构成了一个逆序对，所以我们只需要求出以nums[i]为第一个元素的逆序对个数。

求逆序对最经典的方法就是分治，即归并排序。所以这题我们也可以用归并排序，只需要新增一行代码：在进行merge时，记录有多少个以nums[i]开头的逆序对。

时间复杂度为O(nlogn)，空间复杂度为O(n)。

思路三、线段树/树状数组

此题还可以用线段树/树状数组做，我们知道线段树和树状数组可以求前缀和，而这题可以转换成求前缀和。具体转换过程如下：

1. 我们先遍历一遍数组，确定数组中元素的最小值MIN和MAX，然后想象有一个大小为MAX - MIN的全0数组arr，arr[i]=j表示i+MIN出现了j次。然后在这个数组上构建线段树/树状数组；
2. 然后从后往前遍历数组nums，将arr[nums[i]-MIN]++，表示出现次数加1，更新线段树/树状数组，这样就可很方便求得右侧比它小的元素个数。

时间复杂度O(nlogN)，空间复杂度O(N)，其中N = MAX - MIN；

关于线段树和树状数组可参考我的博客Range Sum Query - Mutable (区间查询)

C++

思路一

struct BstNode{
    int val, node_num; // node_num记录这棵树有多少节点
    BstNode *left, *right;
    BstNode(int x): val(x), node_num(1), left(NULL), right(NULL){}
};

class Solution {
private:
    void BST_insert(BstNode *root, BstNode *node){
        root -> node_num += 1;
        if(node -> val >= root -> val){ // 插入到右子树
            if(root -> right) BST_insert(root -> right, node);
            else root -> right = node;
        }
        else{ // 插入到左子树
            if(root -> left) BST_insert(root -> left, node);
            else root -> left = node;
        }
    }
    
    int count(BstNode *root, int target){
        if(!root) return 0;
        
        if(root -> val < target) 
            return 1 + (root -> left == NULL ? 0 : root -> left -> node_num) \
            + count(root -> right, target);

        else return count(root -> left, target);
    }
   
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int>res(nums.size(), 0);
        if(nums.empty()) return res;
        BstNode *root = new BstNode(nums.back());
        for(int i = nums.size() - 2; i >= 0; i--){
            res[i] = count(root, nums[i]);
            BstNode *node = new BstNode(nums[i]);
            BST_insert(root, node);
        }
        return res;
    }
};

思路二

class Solution {
private:
    vector<int>res;
    void merge_sort(vector<pair<int, int>>&nums_with_idx, int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(nums_with_idx, l, mid);
        merge_sort(nums_with_idx, mid+1, r);
        merge(nums_with_idx, l, mid, r);
    }
    
    void merge(vector<pair<int, int>>&nums_with_idx, int l, int mid, int r){
        vector<pair<int, int>>merged;
        int i = l, j = mid + 1;
        while(i <= mid && j <= r){
            if(nums_with_idx[i].first <= nums_with_idx[j].first){ 
                // 与普通归并排序相比新增的一步, 即记录逆序数:
                res[nums_with_idx[i].second] += j - mid - 1; // nums[i]大于nums[mid+1,...,j-1]
                merged.push_back(nums_with_idx[i++]);
            }
            else merged.push_back(nums_with_idx[j++]);
        }
        while(i <= mid){
            res[nums_with_idx[i].second] += j - mid - 1;
            merged.push_back(nums_with_idx[i++]);
        }
        //while(j <= r) merged.push_back(nums_with_idx[j++]);
        for(int k = 0; k < merged.size(); k++) nums_with_idx[k+l] = merged[k];
    }
    
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<pair<int, int>>nums_with_idx;
        res = vector<int>(nums.size(), 0);
        for(int i = 0; i < nums.size(); i++) 
            nums_with_idx.push_back({nums[i], i});
        merge_sort(nums_with_idx, 0, nums.size() - 1);
        return res;
    }
};

思路三、线段树

class SegTree{
private:
    int n; 
    vector<int>tree; // 用一个长为2n的数组来表示树
public:
    SegTree(vector<int>& nums) {
        /* 对数组nums建线段树, 方便求sum(nums[i,...,j])以及更新nums[i]*/
        n = nums.size();
        tree = vector<int>(n*2, 0); 
        
        for(int i = 0; i < n; i++) // 建树
            update(i, nums[i]);
    }
    
    void update(int i, int diff) {
        /*更新操作: 将nums[i]的值加上diff*/
        i += n; // 转换为线段树下标
        while(i > 0){
            tree[i] += diff;
            i >>= 1;
        }
    }
    
    int sumRange(int i, int j) {
        /**求nums[i,...,j]的和*/
        if(i > j) return 0;
        
        i += n; j += n; // 转换为线段树下标
        int res = 0;
        for(; i <= j; i >>= 1, j >>=1){
            if(i & 1) res += tree[i++]; // 是右孩子
            if(!(j & 1)) res += tree[j--];
        }
        return res;
    }
};
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int>res(n, 0);
        if(!n) return res;
        
        int min_num = nums[0], max_num = nums[0];
        for(int &num: nums){
            min_num = min(min_num, num);
            max_num = max(max_num, num);
        }
        
        // nums_for_SegTree[i] = j 表示数字i出现了j次, 初始全0次
        vector<int>nums_for_SegTree(max_num - min_num + 1, 0);

        SegTree st = SegTree(nums_for_SegTree);
          
        for(int i = n - 1; i >= 0; i--){
            res[i] = st.sumRange(0, nums[i] - min_num - 1);
            st.update(nums[i] - min_num, 1); // 出现次数+1, 更新树
        }
        
        return res;
    }
};

思路三、树状数组

来源

class Solution {
public:
    int* tree, n;
    int lowbit(int x){
        return x&(-x);
    }
    void update(int pos, int delta){
        while (pos <= n){
            tree[pos] += delta;
            pos += lowbit(pos);
        }
    }
    int getSum(int pos){
        int ret = 0;
        while (pos){
            ret += tree[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
    vector<int> countSmaller(vector<int>& nums) {
        n = nums.size();
        vector<int> ret(n);
        if (n == 0) return ret;
        
        int minn = -50000, maxx = 50000;
        for (int i=0;i<n;++i){
            maxx = max(maxx, nums[i]);
            minn = min(minn, nums[i]);
        }
        n = maxx - minn + 2;
        tree = new int[n+1];
        memset(tree, 0, sizeof(int)*n);
        for (int i=nums.size()-1;i>=0;--i){
            ret[i] = getSum(nums[i] - minn);
            update(nums[i]-minn+1, 1);
        }
        return ret;
    }
};