题目描述

给出一个整数数组nums，你必须返回一个新的counts数组，counts[i]表示nums[i]的右边有多少个数比自己小。

样例

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5的右边有两个数比5小（2和1）。
2的右边有1个数比2小（1）。
6的右边有1个数比6小（1）。
1的右边没有数比自己小。

算法1

(分治) $O(nlogn)$

类似于求逆序对个数，这个题目求的是每个数字右边比自己大的数的个数，在归并排序的合并的过程中更新自己的counts值，在合并时发现右边的数字比较小时则说明需要更新，具体更新方式见代码。

时间复杂度分析：归并$O(nlogn)$

C++ 代码

class item{
public:
    int val;
    int idx;
    item(int v, int i){
        val = v;
        idx = i;
    }
    item(){
        val = 0;
        idx = 0;
    }
};
class Solution {
public:
    vector<int>res;//记录最后counts数组的结果
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.size() == 0)
            return res;
        vector<item>items;
        for(int i = 0; i < nums.size(); i++){
            res.push_back(0);
            items.push_back(item(nums[i], i));
        }

        mergesort(items, 0, nums.size()-1);
        return res;
    }
    void mergesort(vector<item>& items, int s, int e){
        if(s >= e)
            return;
        int mid = (s + e)/2;
        mergesort(items, s, mid);
        mergesort(items, mid+1, e);
        int p1 = s, p2 = mid+1;
        vector<item>tmp(e-s+1);
        int cur = 0;
        while(p1 <= mid && p2 <= e){
            if(items[p1].val <= items[p2].val){
                tmp[cur++] = items[p1++];
            }
            else{
                tmp[cur++] = items[p2++];
                for(int i = p1; i <= mid; i++)//在归并时发现右边的数字小，则说明左边数组剩下的所有数字都比当前nums[p2]要大，因此需要更新左边数组的res值
                    res[items[i].idx]++;
            }
        }
        while(p1 <= mid){
            tmp[cur++] = items[p1++];
        }
        while(p2 <= mid){
            tmp[cur++] = items[p2++];
        }
        for(int i = 0; i < cur; i++)
            items[i+s] = tmp[i];
    }
};

算法2

(二叉搜索树) $O(nlogn)$

可以这样考虑，从右向左遍历数组，counts数组相当于求已经遍历过的数字里有多少个数比自己小，相当于在动态的插入数字，并且在插入的同时求出有多少个数小于自己，考虑用BST，在插入数字的同时维护每个节点左右子节点包含的数字个数，这样就能在插入数字的同时求出比自己小的数字个数。

时间复杂度分析：每次插入数字并且查询比自己小的数字个数需要logn的复杂度，因此总的复杂度为 $O(nlogn)$。

C++ 代码

class Node{
public:
    Node*left;
    Node*right;
    int leftnum;//左子节点包含的数字个数
    int rightnum;//右子节点包含的数字个数
    int repeat;//自己重复出现的次数
    int val;//自己这个节点的值
    Node(int v){
        val = v;
        repeat = 1;
        leftnum = 0;
        rightnum = 0;
        left = NULL;
        right = NULL;
    }
};
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int>res(nums.size(), 0);
        if(nums.size()==0)
            return res;
        Node*root = new Node(nums[nums.size()-1]);
        for(int i = nums.size()-2; i >= 0; i--){
            res[i] = insert(root, nums[i]);
        }
        return res;
    }
    int insert(Node*root, int num){//将数字插入到bst树中，同时返回现在树中有多少个数字比自己小。
        if(num < root->val){//比当前节点小，往左走
            root->leftnum += 1;
            if(root->left)
                return insert(root->left, num);
            else{
                root->left = new Node(num);
                return 0;
            }
        }
        if(num == root->val){//等于当前节点，repeat+1
            root->repeat += 1;
            return root->leftnum;
        }
        if(num > root->val){//比当前节点大，往右走，注意返回值
            root->rightnum += 1;
            if(root->right)
                return root->leftnum+root->repeat+insert(root->right, num);
            else{
                root->right = new Node(num);
                return root->leftnum+root->repeat;
            }
        }
        return 0;
    }
};