LeetCode面试题51.数组中的反转对

面试题51.数组中的反转对-lcof/title数组中的两个数，如果前一个数大于后一个数，则两个数组成一个反转对.给定一个数组，找到数组中反转对的总数。例1：输入：[7,5,6,4]输出：5解题思路：归并排序归并排序使用了分而治之的思想，而这个过程需要使用递归来实现。在分治算法的递归实现中，每一层递归都包括三个步骤：分解：将原问题分解为一系列的子问题；求解：递归求解每个子问题，如果子问题足够小，直接求解；合并：将子问题的结果合并到原问题中。本题分解：假设区间为[left,right]，设mid=[(left+right)/2]，将[left,right]分为[left,mid]和[mid+1,right]；解决：对两个子序列使用递归排序；Merge：合并已经排好序的子序列[left,mid]和[mid+1,right]题目中要求返回数组中反转对的总数。倒序对：即前一个数大于后一个数，则这两个数可以组成倒序对。具体思路参考代码。代码实现类解决方案：defreversePairs(self,nums:List[int])->int:n=len(nums)ifn<2:return0#合并辅助数组temp=[0]*nreturnself.count_invs(nums,0,n-1,temp)defcount_invs(self,nums,left,right,temp):如果left==right:return0mid=(left+right)//2left_pairs=self.count_invs(nums,left,mid,temp)right_pairs=self.count_invs(nums,mid+1,right,temp)#这表示已经排序了，已经计算了排序前左右部分的倒序pair。invs_pairs=left_pairs+right_pairsifnums[mid]mid:nums[i]=temp[q]q+=1elifq>right:nums[i]=temp[p]p+=1eliftemp[p]<=temp[q]:#这时候，前面部分区间的元素就出队了#因为p对应的元素小于q#对应的元素那么p对应的元素肯定小于q#对应的元素后面的元素所以此时倒序对不算，p往前移动nums[i]=temp[p]p+=1else:#这是相反的情况#p对应的元素比元素大对应q，#那么p对应的元素后面的元素一定更大#所以，元素出队，同时统计逆序对#此时有多少个逆序对数组pos中的元素itionp到区间的末尾，即mid-p+1nums[i]=temp[q]q+=1ans+=(mid-p+1)returnans实现结果以上是用归并排序解决的思路《面试题51. 数组中的逆序对》问题主要内容请关注微信公众号《书所集录》