Hard
首先想到的方法是暴力解，题目没有给出数据规模。但是作为Hard题，暴力解大概率会超时。
尝试一下，果不其然，TLE
python3
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
r = []
for i in range(len(nums)):
t = 0
for j in range(i, len(nums)):
if nums[j] < nums[i]:
t += 1
r.append(t)
return r
阅读大佬解法，获得新思路，使用归并排序求解
这道题本质上说是求逆序数，而逆序数是归并排序的副产物
话不多说，先学一波归并排序：
https://www.interviewbit.com/tutorial/merge-sort-algorithm/ https://www.jianshu.com/p/3ad5373465fd https://www.cnblogs.com/chengxiao/p/6194356.html
学习了归并排序之后再回过头看这道题
逆序数之所以用归并排序来优化，是因为在归并的并的过程中，我们是局部有序的，这样我们就可以直接获得这段中的逆序数逆序数不是完整的，在合并的过程中，数的位置会发生改变。统计的逆序数也会发生改变indexes用来记录所有元素的索引indexes的作用是，在排序的过程中，我们交换的不是数字，是下标。只是交换的时候比较的是原来的数字nums[indexes[i]]和nums[indexes[j]]的比较结果来决定indexes[i]和indexes[j]的先后顺序补充说明
right中的当前数比left的数小是，我们需要使用一个计数变量记录一下，right后面的数都要加上这个计数，因为right中是单调的，后面的数比前面的大，如果一个数比前面的数小，那必然比后面的小以下视屏，讲的很清晰，看两遍就能理解了
参考 happygrilzt
LeetCode 315 Count of Smaller Numbers After Self 中文解释 Chinese Version
以上，尝试写一下代码，AC！
python3
class Solution:
def merge(self,nums, indexes, left, right, res):
i = 0
j = 0
r = []
rightCount = 0
while i < len(left) and j < len(right):
if nums[left[i]] <= nums[right[j]]:
res[left[i]] += rightCount
r.append(left[i])
i += 1
else:
rightCount += 1
r.append(right[j])
j += 1
while i < len(left):
res[left[i]] += rightCount
r.append(left[i])
i += 1
while j < len(right):
r.append(right[j])
j += 1
return r
def mergeSort(self,nums, indexes, start ,end, res):
if end-start <= 1:
return indexes[start:end]
mid = start + (end-start) // 2
left = self.mergeSort(nums, indexes, start ,mid, res)
right = self.mergeSort(nums, indexes, mid , end, res)
return self.merge(nums,indexes,left,right, res)
def countSmaller(self, nums: List[int]) -> List[int]:
indexes = [ i for i in range(len(nums)) ]
res = [ 0 for i in range(len(nums)) ]
r = self.mergeSort(nums,indexes, 0,len(nums), res)
return res