Count of Smaller Numbers After Self

还是个比较难的题，首先O(n^2)的算法大数据会超时，然后这道题尝试了线段树还是无法解决问题（不知道是不是线段树的逻辑还是没缩减时间复杂度），最后只能参考归并排序的思路搞定了这道题，

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        result = [0] * n
        mapping = list(enumerate(nums))

        self.mergeSort(mapping, 0, n, result)
        return result

    def mergeSort(self, nums, start, end, result):
        if start >= end - 1:
            return nums[start:end]

        mid = start + (end - start) / 2
        left = self.mergeSort(nums, start, mid, result)
        right = self.mergeSort(nums, mid, end, result)
        tmp = [0] * (len(left) + len(right))

        leftCur, rightCur = len(left) - 1, len(right) - 1
        tmpCur = leftCur + rightCur + 1
        while leftCur >= 0 and rightCur >= 0:
            if left[leftCur][1] > right[rightCur][1]:
                tmp[tmpCur] = left[leftCur]
                result[left[leftCur][0]] += (rightCur + 1)
                leftCur -= 1
            else:
                tmp[tmpCur] = right[rightCur]
                rightCur -= 1
            tmpCur -= 1

        while leftCur >= 0:
            tmp[tmpCur] = left[leftCur]
            leftCur -= 1
            tmpCur -= 1

        while rightCur >= 0:
            tmp[tmpCur] = right[rightCur]
            rightCur -= 1
            tmpCur -= 1

        return tmp