2020-04-25

针对逆序对。
归并排序，是首先想到的；
而后才是基于二分的插入排序。而后是基于第二种用负数进行倒排。

归并

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        w=0;k=len(nums)
        te=[0]*k
        #te=nums[:]  
        def merges(s,e):
            if s>=e:return
            mid=s+e>>1
            merges(s,mid)
            merges(mid+1,e)
            a=p=s
            b=m=mid+1
            nonlocal w
            while a<=mid and b<=e:
                if nums[a]<=nums[b]:
                    g=a
                    a+=1
                else:
                    w += m-a #理解这里是关键
                    g=b
                    b+=1
                te[p]=nums[g]
                p+=1
            if a<=mid:
                te[p:e+1]=nums[a:mid+1]
            if b<=e:
                te[p:e+1]=nums[b:e+1]
            nums[s:e+1]=te[s:e+1]
        merges(0,k-1)
        return w

w += m-a #理解这里是关键
当b指向的元素需要插入te 中时，所有的在a到mid之间元素都与它构成逆序对。
而他们的个数，就是m-a
这样再后来的两个if 中，不用对w 进行累加了。

大量的引入临时变量，就是为了把每一次计算过的，压缩掉。
f=e+1 把代码控制行数

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        w=0;
        #te=[0]*k
        te=nums[:]  
        def merges(s,e):
            if s>=e:return
            mid=s+e>>1
            merges(s,mid);merges(mid+1,e)
            a=p=s;b=m=mid+1; nonlocal w;f=e+1
            while a<=mid and b<=e:
                if nums[a]<=nums[b]:
                    g=a;a+=1
                else:
                    w += m-a #理解这里是关键
                    g=b;b+=1
                te[p]=nums[g]
                p+=1
            if a<=mid : te[p:f]=nums[a:mid+1]
            if b<=e   : te[p:f]=nums[b:f]
            nums[s:f]=te[s:f]
        merges(0,len(nums)-1)
        return w

基于二分的插入排序，这是我写的

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        ans,t=0,[]
        for i,v in enumerate(nums):
            index = bisect.bisect(t,v)
            ans += i-index
            insort(t,v)
            
        return ans

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        q = []
        res = 0
        for v in nums:
            i = bisect.bisect_left(q,-v)
            res += i 
            q[i:i] = [-v]
        return res

感谢
https://blog.csdn.net/u012626848/article/details/81274872

---

方法二：使用 list【位置：位置】=【元素，元素……】方法

          但是要注意这种方法的使用（我认为与其叫做插入元素，不如叫做设置元素）

当冒号前后位置相同时，在原列表指定位置前插入指定元素，也就是将位置 0 的元素设置为 orange

image

结果：

image