Leetcode 315

这道题真的把我绕进去好久，提交也一直报错，找不出原因orz，一行一行看代码也没看出哪里有问题。栽倒了小细节上。

大概思路是用递归排序，在排序的过程中，可以更新（下标对应的）元素后面有多少个小于自己的数。
用一个新数组[0,1,2,3,...]记录原数组下标。所以，递归排序改变元素位置时，下标也对应移动，以此作为记录答案的依据。

代码如下

def countSmaller(self, nums: List[int]) -> List[int]:
    l = len(nums)
    if l == 0:
        return []
    if l == 1:
        return [0]
    tmp = [0 for _ in range(l)]
    counter = [0 for _ in range(l)]
    index = [i for i in range(l)]
    self.merge_sort(nums, tmp, 0, l - 1, counter, index)

    return counter

def merge_sort(self, array, tmp, start, end, counter, index):
    if start == end:
        return
    mid = (start + end) // 2
    # start =0 end=1 mid=0
    self.merge_sort(array, tmp, start, mid, counter, index)
    self.merge_sort(array, tmp, mid + 1, end, counter, index)
    if array[index[mid]] > array[index[mid + 1]]:
        # 开始执行归并操作，并且在归并过程中统计出右侧小于当前元素的个数
        self.sortAndCount(array, tmp, start, mid, end, counter, index)

def sortAndCount(self, array, tmp, start, mid, end, counter, index):
    for i in range(start, end + 1):
        tmp[i] = index[i]  # 保存一下原始状态（也就是本次调用移动前的状态）

    i = start
    j = mid + 1
    for k in range(start, end + 1):
        if i > mid:
            index[k] = tmp[j]  # 这里的index赋值是更新移动后当前元素原来的下标（即初始数组中的位置）
            j += 1
        elif j > end:
            index[k] = tmp[i]
            counter[index[k]] += end - mid
            i += 1
        elif array[tmp[i]] <= array[tmp[j]]:
            index[k] = tmp[i]
            i += 1
            counter[index[k]] += j - (mid + 1)
        else:
            index[k] = tmp[j]
            j += 1