题目要求出所有元素的其右边比它小的元素个数。
我的解法：
1.先对数组进行排序，然后采用树状数组记录比当前元素出现次数少的元素的个数。如5，4，7，2，排序后为2，4，5，7，那么树状数组记录了0（比2小的元素个数），1（比4小的元素个数），2（比5小的元素个数），3（比7小的元素个数）。
2.查询的时候查询比元素nums[i]小的元素出现次数总和，查询当前元素时，对当前元素的出现次数进行-1操作（同时会更新树状数组），表示当前元素出现在后面元素的前面，后面的元素统计时不应该把这个元素的数量计算进去。
3.按照nums的次序进行查询，这样可以确保已经查询过的元素（即在当前元素左边的元素）在树状数组里面的出现次数也相应减少了，所以可以放心查询比nums[i]元素小的元素个数。
4.排序使用了set，时间复杂度为O（nlogn），后面树状数组查询操作时间复杂度为O(nlogn)。
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].
AC代码：
[c language=”++”]
class Solution {
public:
vector<int> tree;
//树状数组函数：
int lowbit(int x)
{
return (x&-x);
}
void add(int x, int val)
{
for (int i = x; i<tree.size(); i += lowbit(i))
tree[i] += val;
}
int get(int x)
{
int sum = 0;
for (int i = x; i; i -= lowbit(i))
sum += tree[i];
return sum;
}
vector<int> countSmaller(vector<int>& nums) {
set<int> sortNumsSet;
map<int, int> times;
//对nums进行排序和统计
for (int i = 0; i<nums.size(); i++)
{
times[nums[i]]++;
sortNumsSet.insert(nums[i]);
}
//建立树状数组
tree = vector<int>(sortNumsSet.size() + 1, 0);
map<int, int> pos;
vector<int> sortNums(sortNumsSet.size(), 0);
set<int>::iterator ite = sortNumsSet.begin();
//复制到新的数组中，并且记录元素的位置。
for (int i = 0; i<sortNums.size(); i++)
{
sortNums[i] = *ite;
pos[sortNums[i]] = i + 1;
ite++;
add(i + 1, times[sortNums[i]]);
}
vector<int> ans(nums.size(), 0);
for (int i = 0; i<nums.size(); i++)
{
//当前元素的出现次数－1
add(pos[nums[i]], -1);
//获取nums[i]前面的元素总数
ans[i] = get(pos[nums[i]] – 1);
//cout<<ans[i]<<‘ ‘;
}
return ans;
}
};
[/c]