leetcode 计算右侧小于当前元素的个数 python 之利用归并排序的思想

不容易啊
需要记录计数器，还有记录原来的位置，很麻烦

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def merge(A,B,counterA,counterB,indexA,indexB):
            a_cur=0
            b_cur=0
            M=[]
            counterM=[]
            counterM_ind=[]
            while a_cur<len(A) and b_cur<len(B):
                if A[a_cur]<=B[b_cur]:
                    M.append(A[a_cur])
                    counterM.append(counterA[a_cur]+b_cur)
                    counterM_ind.append(indexA[a_cur])
                    a_cur+=1
                else:
                    M.append(B[b_cur])
                    counterM.append(counterB[b_cur])
                    counterM_ind.append(len(A)+indexB[b_cur])
                    b_cur+=1
            if a_cur==len(A):
                M=M+B[b_cur:]
                counterM_ind=counterM_ind+map(lambda x: x+len(A),indexB[b_cur:])
                counterM=counterM+counterB[b_cur:]
            else:
                M=M+A[a_cur:]
                counterM_ind=counterM_ind+indexA[a_cur:]
                counterM=counterM+map(lambda x: x+b_cur,counterA[a_cur:])
            return M,counterM,counterM_ind
        
        def m_sort(X):
            if len(X)==1:
                return X,[0],[0]
            mid_ind=int(len(X)/2)
            left=X[0:mid_ind]
            right=X[mid_ind:]
            A,counterA,indexA=m_sort(left)
            B,counterB,indexB=m_sort(right)
            return merge(A,B,counterA,counterB,indexA,indexB)
        
        if len(nums)==0:
            return nums
        _,counter,index=m_sort(nums)
        res=[0]*len(nums)
        for i in range(len(index)):
            res[index[i]]=counter[i]
        return res