数组中逆序对的个数

分治算法思想的应用

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        result = [0]*len(nums)
        self.mergeSortCounting(nums, 0, len(nums)-1, result)
        return sum(result)
    
    def mergeSortCounting(self, nums, start, end, result):
        if start >= end:
            return
        mid = start + ((end-start)>>1)
        self.mergeSortCounting(nums, start, mid, result)
        self.mergeSortCounting(nums, mid+1, end, result)
        self.merge(nums, start, end, mid,result)
        
    def merge(self, nums, start, end, mid,result):
        i = start
        j = mid+1
        tmp = []
        while i <= mid and j <= end:
            if nums[i] <= nums[j]:
                tmp.append(nums[i])
                i += 1
            else:
                result[i] += (mid-i+1)
                tmp.append(nums[j])
                j += 1
        while i <= mid:
            tmp.append(nums[i])
            i += 1
        while j <= end:
            tmp.append(nums[j])
            j += 1
        nums[start:end+1] = tmp[0:]
        
        
                
                
        
        

典型的题目还有：

1.二维平面上有n个点，如何快速计算出两个距离最近的点对?
2.有两个nn的矩阵A，B，如何快速求解两个矩阵的乘积C=AB?