You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
Subscribe to see which companies asked this question
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
一开始傻傻不懂，直接上暴力，果断超时。
int* countSmaller(int* nums, int numsSize, int* returnSize) {
int *returnsum = (int *)malloc(sizeof(int)*numsSize);
memset(returnsum,0,sizeof(int)*numsSize);
for(int i = 0 ; i < numsSize;i++)
{
int count = 0;
for(int j = i;j
经过了一段思考之后打算从右往左遍历，桶排，每个nums[i]即为数组的下标，这样在计算num[i-1]时，只需找离他最近的数看其对应的值是多少，然后加一返回即可，但是，这种思路没发处理相同数字或者负数的问题。因此借鉴了网上二叉树的思路：
同样是后续遍历，但是每次获得一个value，都把他加进叔里面，小左，右大。在从root往下搜寻比其小的第一个值时，每路过一个root，root自己的统计比自己小的数量加一（注意，此时加一完全是提供给之后的搜寻使用，其smaller已经不是所要的统计值，只统计比自己小的数量，其他的在计算时由比较相加）
这样找到合适的位置，把其值加起来即可返回。动态规划的思路。
class Solution {
public:
struct Node {
int val, smaller;
Node *left, *right;
Node(int value, int small) {
left=right=NULL, val=value, smaller=small;
}
};
int insert(Node *&root, int value) {
if (root==NULL)
return (root=new Node(value, 0)), 0;
if (value < root->val)
return root->smaller++, insert(root->left, value);
else
return insert(root->right, value) + root->smaller + (value>root->val ? 1 : 0);
}
vector
Node *root = NULL;
deque
for (int i=nums.size()-1; i>=0; i--)
ans.push_front(insert(root, nums[i]));
return vector
}
};