剑指51. 归并排序

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

利用归并排序来查找逆序对,思路:

  1. divide部分,先递归将数组分成最小单元的数组,递归出口  start>=end 

    为什么要加等号,因为每次递归是 递归  start,mid  ;  mid+1,end ; 而mid是左中点 比如最后  (7,8)-> (7,7) (8,8)

    递归到最后只会相等,不会start>end 

  2. 递归路径,上面已经说明了,路径有两,一个往左边(start,mid),一个往右边(mid,end)

  3. 递归到最小单元以后开始合并

  4. 合并:

    1) 对于左右两个数组,用两个指针从start->mid, mid+1->end

    2) 谁小,谁就point++

    3) 如果是右边小,那么逆序对就发生了,[3,4,7,8]  [5,6,9,10] ,比如 i = 7 j = 5,逆序发生了

    4) 此时 j+=1 , 那么接下来就是 7与6比较,那么7以后的所有大数都没有机会与5组成逆序对

    5) 所以逆序发生时,self.cnt += mid-i+1

    6)到最后如果数组没有遍历完,其实也不用管,这里还是加上去了,然后修改了Nums

原文地址:https://www.cnblogs.com/ChevisZhang/p/13657316.html