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

难度：困难

题目

给定一个整数数组 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

Reference

题解

基本思路： 从后往前构造一个二叉查找树，在二叉查找树中维护树中小于当前节点的数字的个数。

二叉树需要添加一个域用于计算左子树的元素总数，即当前树中数值小于该节点的元素总数。实现方法是在左子树添加元素后该域的值增加1。

在节点的右子树添加元素时，意味着当前节点和节点左子树中的所有节点都是符合右侧小于当前元素的节点。在递归过程中需要传递一个用作计数器的指针参数（计数的数值即为所求的结果）。

代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode2
{
    struct TreeNode2 *left;
    struct TreeNode2 *right;
    int val;
    int subs;
};

struct TreeNode2 *insert(struct TreeNode2 *dest, int src, int *depth)
{
    if (dest == NULL)
    {
        struct TreeNode2 *ret = (struct TreeNode2 *)malloc(sizeof(struct TreeNode2));
        ret->left = NULL;
        ret->right = NULL;
        ret->val = src;
        ret->subs = 0;
        return ret;
    }
    if (src > dest->val)
    {
        *depth += 1 + dest->subs;
        dest->right = insert(dest->right, src, depth);
    }
    else
    {
        dest->subs++;
        dest->left = insert(dest->left, src, depth);
    }
    return dest;
}

int *countSmaller(int *nums, int numsSize, int *returnSize)
{
    *returnSize = numsSize;
    int *ret = (int *)memset(malloc(sizeof(int) * numsSize), 0, sizeof(int) * numsSize), i = 0;
    if (numsSize <= 1)
        return ret;
    struct TreeNode2 *tempTree = NULL;
    for (i = numsSize - 1; i >= 0; i--)
        tempTree = insert(tempTree, nums[i], ret + i);
    return ret;
}

评论