题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
from re import S
#from re import S
#
#from pandas import test
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def __init__(self):
self.count = 0
#采用分治
def _count(self,nums,start,end):
if start >= end:
return
mid = int((start+end)/2)
#分组左右两个组，并按照大小排序
left = nums[start:mid+1]
right = nums[mid+1:end+1]
left.sort()
right.sort()
i = 0
j = 0
while i<len(left) and j<len(right):
#如果left数组中某一个元素x大于right中某一个，测说明left中x之后的元素都满足条件
if left[i]>right[j]:
self.count += (len(left)-i)
j+=1
else:
i+=1
self._count(nums,start,mid)
self._count(nums,mid+1,end)
def InversePairs(self , nums) -> int:
self._count(nums,0,len(nums)-1)
return self.count%1000000007
