Leetcode之计算右侧小于当前元素的个数_列表所有右边比左边小的数个数

题目：

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
 

提示：

0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

代码：

方法一——暴力模拟法：

暴力模拟法思路非常简单，就是每次都从末尾找比num[i]小的数并计数，然后放到结果数组即可。

vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
        vector<int>ans(n,0);
        int t;
        for(int i=n-2;i>=0;i--){
            t=0;
            for(int j=n-1;j>i;j--){
                if(nums[j]<nums[i])
                    t++;
            }
            ans[i]=t;
        }
        return ans;
    }

方法二——模拟法+查找：

我们从暴力模拟法为起点进一步优化，我们看到每次我们都要从末尾遍历相同的元素，实际上我们可以建立一个保持排序的数组sorted_num。
这个数组代表：在nums[i]之后所有的数，并且已经排好序。
每次在nums数组出现新的需要判断的数就要插入到这个sorted_num，然后在这个数通过二分查找到下界(可以用STL自带的lower_bound()) 减去sorted_num.begin()就是比nums[i]小的元素个数了。

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
    vector<int> sorted_num;
    /*建立一个保持排序的数组*/
    vector<int> res;
    /*用于保存结果的数组*/
    for(int i=nums.size()-1;i>=0;i--){
        auto iter = lower_bound(sorted_num.begin(),sorted_num.end(),nums[i]);
        /*通过lower_bound()二分寻找下界，返回一个迭代器(也就是相对于sorted_num的index)*/
        int pos = iter-sorted_num.begin();
        /*
        通过排序数组的二分查找性质，我们可以知道iter-sorted_num.begin()(可以理解成sorted_num数组的起始位置)就是
        题目需要的比nums[i]小的数字个数
        */
        sorted_num.insert(iter,nums[i]);
        /*这时nums[i]已经使用完了，需要给以后的数字拿来判断
        插入后要保持sorted_num排序，所以nums[i]插入到iter位置*/
        res.push_back(pos);
    }
    reverse(res.begin(),res.end());
    /*一路上都是倒序插入的，所以在最后要逆转数组*/
    return res;
}
};

class Solution {
 public:
     vector<int> countSmaller(vector<int>& nums) {
         vector<int>t,res(nums.size());　　　　　　/*初始化t,res*/
         for(int i=nums.size()-1;i>=0;i--){
             int left=0,right=t.size();　　　　　　　　/*下面是一个在t数组里二分查找的过程*/
             while (left<right){
                 int mid=left+(right-left)/2;
                 if(t[mid]>=nums[i]){
                     right= mid;
                 }
                 else{
                     left=mid+1;
                 }
             }
             res[i]=right;
             t.insert(t.begin()+right,nums[i]);
         }
         return res;
     }
 };

方法三——记忆化+排序：

还有个很第二种方法比较类似的方法，就是用STL的pari记录:没有排序前每个num[i]对应的下标i,pair<int,int>:nums[i]->i。

记录完之后进行排序。 然后利用已排序的性质进行查找，代码有些复杂且用到了一些位操作的知识，比较难想到，但也是一种非常好的方法。

const int MAXN = 100007;
 
int cnt[MAXN],n;
/*数组cnt[i]用于记录出现元素nums[i]的个数*/
class Solution {
public:
    inline void add(int k)
    {
        for(; k <= n; k += -k&k) cnt[k] += 1;
    }
 
    int sum(int k)
    {
        int res = 0;
        for(; k; k -= -k&k) res += cnt[k];
        return res;
    }
 
    vector<int> countSmaller(vector<int>& nums) {
        n = nums.size();
        vector<int> ans(n);
        vector<pair<int, int>> A;
        /*建立一个从数组内容到未排序前索引的映射A*/
        for(int i = 0; i < n; i ++) {
            A.push_back({nums[i], i+1});
        }
        memset(cnt, 0, sizeof(cnt));
        sort(A.begin(), A.end());
        /*进行排序*/
        for(int i = 0; i < n; i ++) {
            int id = A[i].second;
            int t = sum(n) - sum(id);
            ans[id-1] = t;
            add(id);
        }
        return ans;
    }
};

方法四——二叉搜索树:

作为一个经常刷leetcode的人来说，刚开始看到这种方法简直是跪着看完的。建立一个二叉搜索树，每个树的结点都有变量val这个结点的值和变量count记录小于该结点的个数。
因为count的最后一个值的结果一定是0，所有先把0放入count数组，并建立一个以val为nums[i-1]的单独结点树。

逆序读nums[i]并建立二叉搜素树，首先排除nums.size()==0的情况，每读取一个nums[i]，先去搜索树寻找这个nums[i]对应的答案，
找到答案之后返回给引用参数count_small，再把nums[i]这个值作为新的结点的val插入。 
最后需要将树的结点delete以防内存浪费。

struct BSTNode{
    int val;
    int count;
    BSTNode *left;
    BSTNode *right;
    BSTNode(int x)
    : val(x)
    , left(NULL)
    , right(NULL)
    , count(0)
    {}
};
/*建立一个二分查找树，每个树结点有四个值,分别是:
 int val;这个结点代表的值val
 int count;这个val代表的次数也就是在nums数组种比val小的数的个数
 left 左子树指针
 right 右子树指针
 一个构造函数，构造函数如上定义
 */
 
void BST_insert(BSTNode *node,BSTNode *insert_node,int &count_small)
{
    if(node->val >= insert_node->val)
    {
        /*插入的结点更小,被比较结点(即node)的count++，然后插入到左子树(如果不为空)*/
        node->count++;
        if(node->left)
        {
            BST_insert(node->left,insert_node,count_small);
        }
        else
        {
            /*左子树为空，插入结点就作为当前结点的左孩子*/
            node->left = insert_node;
        }
    }
    else{
        /*插入的结点更大，需要在右子树(如果不为空)继续找*/
        count_small += node->count + 1;
        if(node->right)
        {
            BST_insert(node->right,insert_node,count_small);
        }
        else
        {
            /*当前右子树为空，插入结点作为当前结点右孩子*/
            node->right = insert_node;
        }
    }
}
/*count_small作为一个引用的参数，在递归寻找子树的时候作为一个“类似全局变量”的存在*/
 
 
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
        /*如果数组为空返回空值*/
        if(n==0)return {};
        vector<int> count;
        count.push_back(0);
        /*建立一个二叉搜素树*/
        BSTNode* node=new BSTNode(nums[n-1]);
        int count_small;
        for(int i = 1;i < n;i++)
        {
            count_small = 0;
            BST_insert(node,new BSTNode(nums[n-i-1]),count_small);
            count.push_back(count_small);
        }
        /*最后不要忘记删除树节点*/
        delete node;
        reverse(count.begin(),count.end());
        /*push_back的时候是逆序的，此时只要将count数组reverse即可*/
        return count;
    }
};

方法五——利用归并排序:

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]);           
        }
    }
};

方法六——使用树状数组：

这种解法比较少见，速度却是惊人的快。

　　树状数组中getSum(index)作用是求原始数组nums中小于或等于当前index的数的和，此处用来统计逆序数，可以把getSum(x)看作是nums中小于x的数的个数的和。

  以题目中的测试数据[5, 2, 6, 1]为例：

• 初始状态数组c中元素全部置为0
• 插入5时，大于等于5的所有记录的值+1，此时比5小的数的个数为0；
• 插入2时，大于等于2的所有记录的值+1，此时比2小的数的个数为0，比5小的数的个数为1；
• 插入6时，大于等于6的所有记录的值+1，此时比6小的数的个数为2(getSum(6-1)=2)，比2小的数的个数为0，比5小的数的个数为1(getSum(5-1)=1)；
• 插入1时，大于等于1的所有记录的值+1，此时比1小的数的个数为0，比6小的数的个数为3(getSum(6-1)=3)，比2小的数的个数为1(getSum(2-1)=1)，比5小的数的个数为2(getSum(5-1)=2)；

  可以看出当把每个数都遍历一遍后，数组arr中分别记录了比每个数小的数的个数之和，题目要求每个数右侧比它小的数的个数，因此用总数减掉每个数左侧比它小的数的个数就可得到。

　　从插入元素的过程可以看出，每次插入一个元素时，数组arr中记录的值刚好是插入当前元素之前比该元素小的元素的个数（即当前元素左侧比它小的元素个数），因此只需要在插入一个数之前做一次求和，并用一个数组记录该值即可。

class Solution {
public:
    int *arr, n;
    int lowbit(int x){
        return x&(-x);
    }
    void update(int pos, int delta){
        while (pos <= n){
            arr[pos] += delta;
            pos += lowbit(pos);
        }
    }
    int getSum(int pos){
        int ret = 0;
        while (pos){
            ret += arr[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 = 999999999, maxx = -999999999;
        for (int i=0;i<n;++i){
            maxx = max(maxx, nums[i]);
            minn = min(minn, nums[i]);
        }
        n = maxx - minn + 2;
        arr = new int[n];
        memset(arr, 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;
    }
};