036. 数组中的逆序对

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数 P。并将 P 对 1000000007 取模的结果输出。即输出 P % 1000000007。

输入描述：

题目保证输入的数组中没有的相同的数字
数据范围：
	对于%50的数据,size<=10^4
	对于%75的数据,size<=10^5
	对于%100的数据,size<=2*10^5

示例：

# 输入
1,2,3,4,5,6,7,0
# 输出
7

Solutions

首先暴力法求一波：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if data is None:
            return 0
        count = 0
        length = len(data)
        for i in xrange(length - 1):
            for j in xrange(i + 1, length):
                if data[i] > data[j]:
                    count += 1
        return count % 1000000007

太慢，牛客平台都报超时了。

巧妙的方法：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if data is None:
            return 0
        count = 0
        copy = []
        for i in range(len(data)):
            copy.append(data[i])
        copy.sort()
        i = 0
        while len(copy) > i:
            count += data.index(copy[i])
            data.remove(copy[i])
            i += 1
        return count % 1000000007

第三种方法是利用归并排序的方法：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        if len(data)<=0:
            return 0
        length=len(data)
        copy=[0]*length
        for i in range(length):
            copy[i]=data[i]
        #copy数组为原数组data的复制,在后面充当辅助数组
        count=self.Core(data,copy,0,length-1)
        return count % 1000000007
    
    def Core(self,data,copy,start,end):
        if start==end:
            copy[start]=data[start]
            return 0

        length=(end-start)//2 #length为划分后子数组的长度

        left=self.Core(copy,data,start,start+length)
        right=self.Core(copy,data,start+length+1,end)

        #初始化i为前半段最后一个数字的下标
        i=start+length
        #初始化j为后半段最后一个数字的下标
        j=end

        #indexCopy为辅助数组的指针，初始化其指向最后一位
        indexCopy=end
        #准备开始计数
        count=0
        #对两个数组进行对比取值的操作：
        while i>=start and j>=start+length+1:
            if data[i]>data[j]:
                copy[indexCopy]=data[i]
                indexCopy-=1
                i-=1
                count += j-start-length
            else:
                copy[indexCopy]=data[j]
                indexCopy-=1
                j-=1
        
        #剩下一个数组未取完的操作：
        while i>=start:
            copy[indexCopy]=data[i]
            indexCopy-=1
            i-=1
        while j>=start+length+1:
            copy[indexCopy]=data[j]
            indexCopy-=1
            j-=1
        
        return count+left+right

Solutions

References