315. Count of Smaller Numbers After Self

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

Posted by bbkgl on July 11, 2020

明月不谙离恨苦

斜光到晓穿朱户

以前刷PAT的时候经常能做到二叉搜索树的题了,现在刷leetcode蛮难遇到的。

理解这道题能用BST做的关键在于理解插入顺序应该是倒序。

首先肯定的是,可以利用BST的特性,在树中每次插入结点时,都更新各个结点 “索引大于该结点且值小于该结点的个数”,即遍历每个位于该结点右侧的结点,修改右侧每个结点的“索引大于该结点且值小于该结点的个数”。

显然这样子的复杂度偏高,反正我超时了,也就是这个版本。

struct BSTNode {
    BSTNode *left, *right;
    int val;
    int index;

    explicit BSTNode(int x, int i) : val(x), index(i), left(nullptr), right(nullptr) {}
};


class Solution {
private:
    void dfs(BSTNode *root, vector<int> &ans) {
        if (root == nullptr)
            return ;
        ans[root->index]++;
        dfs(root->left, ans);
        dfs(root->right, ans);
    }

    BSTNode *insertx(BSTNode *root, int x, const int index, vector<int> &ans) {
        if (root == nullptr)
            return new BSTNode(x, index);
        if (x >= root->val)
            root->right = insertx(root->right, x, index, ans);
        else {
            ans[root->index]++;
            dfs(root->right, ans);
            root->left = insertx(root->left, x, index, ans);
        }
        return root;
    }

public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size(), 0);
        BSTNode *root = nullptr;
        for (int i = 0; i < nums.size(); i++) {
            root = insertx(root, nums[i], i, ans);
        }
        return ans;
    }
};

简单来说“又臭又长又慢”。。。但是还算好理解的。

如何解决超时问题呢?

答:倒序遍历 nums 数组,这样在插入结点时,保证了树中已经安置的结点都是该结点右侧的结点,这样就不再需要比较其索引。递归插入每个新结点时,如果新结点大于当前根结点,且当前根结点肯定在新结点右侧,就可以直接加上根结点的 cnt 并加1,就能得到新结点“索引大于新结点且值小于新结点的个数”;反之,则将当前根结点的 cnt 加1,因为新结点要插入根结点的左儿子中。

然后每次插入都会计算出新结点“索引大于新结点且值小于新结点的个数”,也就是答案。

总结就是两点:

  • 维护BST,BST每个结点会统计左儿子结点的个数
  • 每次插入新结点时,就能得到新结点“索引大于新结点且值小于新结点的个数”,因为倒数插入此时树中存在的结点全都在新结点的右边

代码如下:

struct BSTNode {
    BSTNode *left, *right;
    int val;
    int cnt;

    explicit BSTNode(int x) : val(x), cnt(0), left(nullptr), right(nullptr) {}
};


class Solution {
private:
    BSTNode *insertx(BSTNode *root, int x, const int index, vector<int> &ans) {
        if (root == nullptr)
            return new BSTNode(x);
        if (x > root->val) {
            ans[index] += root->cnt + 1;
            root->right = insertx(root->right, x, index, ans);
        }
        else {
            root->cnt++;
            root->left = insertx(root->left, x, index, ans);
        }
        return root;
    }

public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size(), 0);
        BSTNode *root = nullptr;
        for (int i = nums.size() - 1; i >= 0; i--) {
            root = insertx(root, nums[i], i, ans);
        }
        return ans;
    }
};