# 315. Count of Smaller Numbers After Self

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:

``````Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.
``````

``````// Binary Search
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int left = 0, right = t.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (t[mid] >= nums[i]) right = mid;
else left = mid + 1;
}
res[i] = right;
t.insert(t.begin() + right, nums[i]);
}
return res;
}
};
``````

``````// Insert Sort
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
res[i] = d;
t.insert(t.begin() + d, nums[i]);
}
return res;
}
};
``````

``````// Binary Search Tree
class Solution {
public:
struct Node {
int val, smaller;
Node *left, *right;
Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
};
int insert(Node*& root, int val) {
if (!root) return (root = new Node(val, 0)), 0;
if (root->val > val) return root->smaller++, insert(root->left, val);
return insert(root->right, val) + root->smaller + (root->val < val ? 1 : 0);
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> res(nums.size());
Node *root = NULL;
for (int i = nums.size() - 1; i >= 0; --i) {
res[i] = insert(root, nums[i]);
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/315

Count of Range Sum

Queue Reconstruction by Height

Reverse Pairs

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76576/My-simple-AC-Java-Binary-Search-code

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/138154/The-C%2B%2B-merge-sort-template-for-pairs-'i'-'j'-problem

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76611/Short-Java-Binary-Index-Tree-BEAT-97.33-With-Detailed-Explanation

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76657/3-ways-(Segment-Tree-Binary-Indexed-Tree-Binary-Search-Tree)-clean-python-code

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76607/C%2B%2B-O(nlogn)-Time-O(n)-Space-MergeSort-Solution-with-Detail-Explanation

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation