计算自己后面有多少比自己小的数字。
给你一个都是数字的数组nums，返回一个新的数组counts，这个数组中的元素 counts[i] 为 nums[i] 右边有多少个比他小的数。
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The countsarray 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.
感觉so easy呀 怀疑怎么可能是hard。结果悲剧了。
public IList<int> CountSmaller(int[] nums) {
IList<int> res=new List<int>();
for(int i=0;i<nums.Length;i++){
int smaller=0;
for(int j=i+1;j<nums.Length;j++){
if(nums[j]<nums[i]){
smaller++;
}
}
res.Add(smaller);
}
return res;
}
Time Limit Exceeded
有没有大佬给指点一二？ 先谢谢了~

这题打字说太困难了。要用到merge sort的思想。时间是nlgn
之后比这个数小的个数，本质上是排序时有多少数字翻转到这个数之前了。
其他的一些解法也有，但在最坏情况也是n平方。

感谢~ 前一段时间 俺贴吧账户被封了。刚刚活过来。
大O表示法又去重学了一下。快速排序的是O(n*logn) 还有一个更快的继续学习。
最近leetcode总刷题数有100+了。 不过前五六十道 都是硬算的。后面100-200的路上继续。 感觉高级我还是吸收不下。还是啃medium。