题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路：
class Solution: def InversePairs(self, data): # write code here return self.inverseCount(data[:], 0, len(data)-1, data[:])%1000000007 def inverseCount(self, tmp, start, end, data): if end-start <1: return 0 if end - start == 1: if data[start]<=data[end]: return 0 else: tmp[start], tmp[end] = data[end], data[start] return 1 mid = (start+end)//2 cnt = self.inverseCount(data, start, mid, tmp) + self.inverseCount(data, mid+1, end, tmp) # print(start, mid, end, cnt, data) i = start j = mid + 1 ind = start while(i <= mid and j <= end): if data[i] <= data[j]: tmp[ind] = data[i] i += 1 else: tmp[ind] = data[j] cnt += mid - i + 1 j += 1 ind += 1 while(i<=mid): tmp[ind] = data[i] i += 1 ind += 1 while(j<=end): tmp[ind] = data[j] j += 1 ind += 1 return cnt
还有一个更简洁的方法，时间复杂度也是nlogn
先将原序列排序，然后从排完序的数组中取出最小的，它在原数组中的位置表示有多少比它大的数在它前面，每取出一个在原数组中删除该元素，保证后面取出的元素在原数组中是最小的，这样其位置才能表示有多少比它大的数在它前面，即逆序对数。
代码如下：
class Solution: def InversePairs(self, data): count = 0 copy = [] for i in data: copy.append(i) copy.sort() for i in range(len(copy)): count += data.index(copy[i]) data.remove(copy[i]) return count%1000000007
原文：https://www.cnblogs.com/tsdblogs/p/10657038.html