剑指offer之035-数组中的逆序对

题目描述

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

数据范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

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

思路

暴力法时间复杂度是o(n^2),超时。

考虑一下,逆序是说a[i]>a[j],i<j。那么在排序的过程中,会把a[i]和a[j]交换过来,这个交换的过程,每交换一次,就是一个逆序对的“正序”过程。

排序每个数,归并排序。


#  234 345
#  233445
def MergeElem(data, start, mid, end, temp):  # data[start...mid], data[mid+1...end]
    cnt = 0
    i = start
    j = mid + 1
    k = start
    while i <= mid and j <= end:
        if data[j] < data[i]:  # data[start...i...mid] data[mid+1...j...end]
            temp[k] = data[j]
            cnt += j - k
            j += 1
            k += 1
        else:
            temp[k] = data[i]
            i += 1
            k += 1
    while i <= mid:
        temp[k] = data[i]
        i += 1
        k += 1
    while j <= end:
        temp[k] = data[j]
        j += 1
        k += 1
    data[start:end+1] = temp[start:end+1]
    return cnt

def InverseCore(data, start, end, temp):
    cnt = 0
    if start < end:
        mid = (start + end) // 2
        cnt += InverseCore(data, start, mid, temp)
        cnt += InverseCore(data, mid+1, end, temp)
        cnt += MergeElem(data, start, mid, end, temp)
    return cnt

def InversePairs(data):
    # write code here
    temp = data[:]
    count = InverseCore(data, 0, len(data)-1, temp)
    return count

print(InversePairs([1,2,3,5,4,6,7,0]))

关于明柳梦少

坚守自己的原则,不随波逐流。