计算右侧小于当前元素的个数_统计数组中右边比小的

这道题利用归并排序，几乎和归并排序一样，不同的地方在于将两个有序数组合并的地方需要添加几行代码。

所以我们要找出规律，举例如下：

在归并两排序数组时，当需要将前一个数组元素的指针 i 指向的元素插入时，它对应的 count[i] ，就是后一个数组的指针j 的值

//count: 0 0 0 0     0 0 0 0 
//nums: -7 1 5 9    -2 1 3 5
//           i             j=3

比如此时到了5这个数，它的count就是3 = j,比5小的数的个数就+3

因为在左边数组sub_vec1，已经有序了，所以比5小的数，且在5右边的，也就只能从sub_vec2中找，sub_vec[2]，也就是5，和sub_vec[j]比较时，比5小的话，j就会后移，j++，所以就有了上面那条规律。

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int>count;//保存结果
        vector<pair<int,int> > num;//关联每个数和它的序号
        for(int i =0;i<nums.size();++i)
        {
            count.push_back(0);
            num.push_back(make_pair(nums[i],i));//保存每个数和它在原数组中的序号，以免在排序过程中打乱顺序
        }
        merge_sort(num,count);
        return count;
    }
    
    //归并排序
    void merge_sort(vector<pair<int,int> >& vec, vector<int>& count)
    {
        if(vec.size()<2)
            return;
        
        int mid = vec.size()/2;
        vector<pair<int,int> > sub_vec1;
        vector<pair<int,int> > sub_vec2;
        for(int i =0;i<mid;++i)
            sub_vec1.push_back(vec[i]);
        for(int i =mid;i< vec.size();++i)
            sub_vec2.push_back(vec[i]);
        
        merge_sort(sub_vec1,count);
        merge_sort(sub_vec2,count);
        vec.clear();
        merge(sub_vec1,sub_vec2,vec,count);
    }
    
    //合并两数组
    void merge(vector<pair<int,int> >& sub_vec1,vector<pair<int,int> >& sub_vec2, vector<pair<int,int> >& vec, vector<int>& count)
    {
        int i =0;
        int j =0;
        while(i < sub_vec1.size() && j < sub_vec2.size())
        {
            if(sub_vec1[i].first <= sub_vec2[j].first )
            {
                vec.push_back(sub_vec1[i]);
                count[sub_vec1[i].second] += j;//这句话和下面注释的地方就是这道题和归并排序的主要不同之处
                i++;
            }else{
                vec.push_back(sub_vec2[j]);
                
                j++;
            }
        }
        
        for(;i<sub_vec1.size();++i)
        {
            vec.push_back(sub_vec1[i]);
            count[sub_vec1[i].second] += j;// -。-
        }
        for(;j<sub_vec2.size();++j)
        {
            vec.push_back(sub_vec2[j]);           
        }
    }
};

方法二：用二叉查找树

将Nums逆置，count[i]就变成了nums[0]...nums[i-1]中有多少个比nums【i】小的数

将元素按照逆置后的顺序插入到二叉查找树，在插入结点时，当待插入结点值小于等于当前结点时，node->count++

大于当前结点时，count_small+=node->count+1;

struct BSTNode{
    int val;
    int count;//二叉树左子树中节点的个数
    BSTNode* left;
    BSTNode* right;
    BSTNode(int x):val(x),count(0),left(NULL),right(NULL){}
};
 
class Solution {
public:
    void BST_insert(BSTNode* node,BSTNode* insert_node,int& count_small)//count_small，二叉排序树中比插入节点值小的结点个数
    {
        if(insert_node->val <= node->val)
        {
            node->count++;
            if(node->left)
                BST_insert(node->left,insert_node,count_small);
            else
                node->left = insert_node;
        }else{
            count_small = count_small + node->count + 1;
            if(node->right)
                BST_insert(node->right,insert_node,count_small);
            else
                node->right = insert_node;
        }
    }
    
    
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res;//最后的结果
        vector<BSTNode*> node_vec;//创建的二叉查找树的结点池
        vector<int> count;//count_small数组
        
        for(int i = nums.size() - 1;i>=0;--i)
            node_vec.push_back(new BSTNode(nums[i]));
        
        count.push_back(0);//第一个结点的count_small为0
        for(int i = 1;i<node_vec.size();++i)
        {
            int count_small = 0;
            BST_insert(node_vec[0],node_vec[i],count_small);
            count.push_back(count_small);
        }
        
        for(int i =node_vec.size()-1;i>=0;--i)
            res.push_back(count[i]);//将结果顺序调换为原来的顺序
        
        return res;
    }
};