[LeetCode 315] 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数

方法一：改进归并排序

预备知识：归并排序

复杂度为

//用双指针把两个有序数组合并成一个有序数组
void merge_sort_two_vector(vector<int> &sub_vec1, vector<int> &sub_vec2,
                            vector<int> &vec) {
    int i = 0, j = 0;
    while (i < sub_vec1.size() && j < sub_vec2.size()) {
        if (sub_vec1[i] <= sub_vec2[j])
            vec.push_back(sub_vec1[i++]);
        else
            vec.push_back(sub_vec2[j++]);
    }
    for (; i < sub_vec1.size(); i++)
        vec.push_back(sub_vec1[i]);
    for (; j < sub_vec2.size(); j++)
        vec.push_back(sub_vec2[j]);
}
//分治解决
void merge_sort(vector<int> &vec) {
    if (vec.size() < 2)
        return;

    int mid = vec.size() / 2;
    vector<int> sub_vec1, sub_vec2;
    sub_vec1.insert(sub_vec1.begin(), vec.begin(), vec.begin() + mid);
    sub_vec2.insert(sub_vec2.begin(), vec.begin() + mid, vec.end());
    merge_sort(sub_vec1);
    merge_sort(sub_vec2);
    vec.clear();
    merge_sort_two_vector(sub_vec1, sub_vec2, vec);
}

为什么复杂度是O(n*logn)？

本题思路：3h3min处

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


struct BSTNode {
    int val;
    int cnt;
    BSTNode *left;
    BSTNode *right;
    BSTNode(int x) : val(x), left(NULL), right(NULL),cnt(0) {}
};

class Solution {
public:
    void BST_insert(BSTNode *node,BSTNode *insert_node,int &count_small) {
        if(insert_node->val<=node->val) {
            node->cnt++;
            if(node->left)
                BST_insert(node->left,insert_node,count_small);
            else
                node->left=insert_node;
        } else {
            count_small=count_small+node->cnt+1;
            if(node->right)
                BST_insert(node->right,insert_node,count_small);
            else
                node->right=insert_node;
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        int count_small=0;
        int len=nums.size();
        vector<int>res(len);
        if(len==0)return res;
        BSTNode *root=new BSTNode(nums[len-1]);
        res[len-1]=count_small;

        for(int i=len-2; i>=0; i--) {
            BSTNode *node=new BSTNode(nums[i]);
            count_small=0;
            BST_insert(root,node,count_small);
            res[i]=count_small;
        }
        return res;
    }
};

int main() {
    vector<int>nums= {5,-7,9,1,3,5,-2,1};
        //期望输出：[5,0,5,1,2,2,0,0]
    Solution s;
    vector<int>res=s.countSmaller(nums);
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }

    return 0;
}