# 计算右侧小于当前元素的个数
给你`一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1]
输出：[0]
示例 3：
输入：nums = [-1,-1]
输出：[0,0]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
vector res;
vector nums = {5, 2, 6, 1};
res = sol.countSmaller(nums);
for (auto i : res)
cout << i << " ";
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
int lowbit(int x)
{
return (int)x & (-1 * x);
}
int getSum(int x, vector &c)
{
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i))
{
sum += c[i];
}
return sum;
}
void update(vector &c, int x, int v)
{
for (int i = x; i < c.size(); i += lowbit(i))
{
c[i] += v;
}
}
vector countSmaller(vector &nums)
{
vector count;
set ss;
for (auto t : nums)
{
ss.insert(t);
}
unordered_map m;
int n = ss.size();
auto it = ss.begin();
for (int i = 1; i <= n; i++)
{
it++;
m[*it] = i;
}
vector sum(n + 1, 0);
for (auto it = nums.rbegin(); it != nums.rend(); it++)
{
int res = 0;
int idx = m[*it];
if (idx > 1)
{
res = getSum(idx - 1, sum);
}
update(sum, m[*it], 1);
count.push_back(res);
}
reverse(count.begin(), count.end());
return count;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector countSmaller(vector &nums)
{
vector res(nums.size(), 0);
vector indexs(nums.size(), 0);
for (int i = 0; i < indexs.size(); i++)
{
indexs[i] = i;
}
vector tempindexs(indexs.size(), 0);
mergeSort(nums, indexs, tempindexs, res, 0, nums.size() - 1);
return res;
}
void mergeSort(vector &nums, vector &indexs, vector &tempindexs, vector &res, int left, int right)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(nums, indexs, tempindexs, res, left, mid);
mergeSort(nums, indexs, tempindexs, res, mid + 1, right);
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right)
{
if (nums[indexs[i]] > nums[indexs[j]])
{
for (int k = i; k <= mid; k++)
{
res[indexs[k]]++;
}
tempindexs[t++] = indexs[j++];
}
else
{
tempindexs[t++] = indexs[i++];
}
}
while (i <= mid)
{
tempindexs[t++] = indexs[i++];
}
while (j <= right)
{
tempindexs[t++] = indexs[j++];
}
t = 0;
while (left <= right)
{
indexs[left++] = tempindexs[t++];
}
}
};
```
### B
```cpp
struct BSTNode
{
int val;
int count;
BSTNode *left;
BSTNode *right;
BSTNode(int x) : val(x), left(NULL), right(NULL), count(0) {}
};
void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small)
{
if (node->val >= insert_node->val)
{
node->count++;
if (node->left)
BST_insert(node->left, insert_node, count_small);
else
node->left = insert_node;
}
else
{
count_small += node->count + 1;
if (node->right)
BST_insert(node->right, insert_node, count_small);
else
node->right = insert_node;
}
}
class Solution
{
public:
vector countSmaller(vector &nums)
{
int n = nums.size();
if (!n)
return {};
vector count;
count.push_back(0);
BSTNode *node = new BSTNode(nums[n - 1]);
int count_small;
for (int i = 1; i < n; ++i)
{
count_small = 0;
BST_insert(node, new BSTNode(nums[n - i - 1]), count_small);
count.push_back(count_small);
}
delete node;
reverse(count.begin(), count.end());
return count;
}
};
```
### C
```cpp
class Solution
{
public:
vector help;
vector countSmaller(vector &nums)
{
int n = nums.size();
if (n == 0)
return vector();
vector res(n, 0);
for (int i = n - 1; i >= 0; --i)
{
auto it = lower_bound(help.begin(), help.end(), nums[i]);
res[i] = it - help.begin();
help.insert(it, nums[i]);
}
return res;
}
};
```