八十二、归并排序求取复杂的逆序数

@Author：Runsen

逆序数，我在很多的面试题都见过，本质上来说难度是比较大，因为如果使用暴力法当数据量一大，必然就会爆掉。你现在就要记住逆序数就是考归并排序。

逆序数

给定一个数组array[0,…,n-1], 若对于某两个元素array[i],array[j],若i<j and array[i]>array[j],

则认为array[i],array[j]是逆序对。一个数组中包含的逆序对的数目称为该数组的逆序数。设计一个算法求一个数组的逆序数

比如给出数组nums = [11, 8, 3, 9, 7, 1, 2, 5]，我可以求出[(11, 8), (8, 3), (11, 3), (11, 9), (7, 1), (7, 2), (7, 5), (3, 1), (8, 1), (9, 1), (11, 1), (3, 2), (8, 2), (9, 2), (11, 2), (8, 5), (9, 5), (11, 5), (8, 7), (9, 7), (11, 7)]

采用暴力破解的话，代码非常简单。

r = []
def reversePairs
  

 

  
1
 

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/111711669