subject ：
Two numbers in an array if the first number is greater than the next number , Then these two numbers form a reverse order pair .
Enter an array , Find the total number of reverse pairs in this array . Make sure that the same number is not in the input array .
Data range
Given the length of the array [0,100].
for example ：
Input ：[1,2,3,4,5,6,7,0]
Output ：7
Input ：[1,2,3]
Output ：0Ideas ： recursive + Sort （ Merger ）
The comparison process , Also the original list Sorted , Calculation count More operations can be omitted .
Code ：
class Solution:
def __init__(self):
self.count = 0
def merge(self , data):
n = len(data)
if n <= 1:
return data
half = n // 2
left = self.merge(data[:half] )
right = self.merge(data[half:])
lo_l = lo_r = 0
res = [] # Save the merged and sorted list
while lo_l < len(left) and lo_r < len(right):
if left[lo_l] < right[lo_r]:
res.append(left[lo_l]) # a1
lo_l +=1
elif left[lo_l] > right[lo_r]:
res.append(right[lo_r]) # a2. a1,a2 Equivalent to comparing two list, From small to large, join in res Of list in .
self.count += len(left[lo_l:])
lo_r += 1
res += left[lo_l:]
res += right[lo_r:] # The rest of the list Add to res in , final res It is an incremental sort list
return res
a = [5,4,2,6,3]
s = Solution()
s.merge(a)
print(s.count)Output ：
6
