劍指Offer（35）：數(shù)組中的逆序對

一、引子

這個系列是我在?？途W(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。
查看完整的劍指Offer算法題解析請點擊CSDN和github鏈接：
劍指Offer完整習題解析CSDN地址
github地址

二、題目

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序對。輸入一個數(shù)組,求出這個數(shù)組中的逆序對的總數(shù)P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007

輸入描述：

題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：

對于%50的數(shù)據(jù),size<=10^4

對于%75的數(shù)據(jù),size<=10^5

對于%100的數(shù)據(jù),size<=2*10^5

事例1：

輸入：

1,2,3,4,5,6,7,0

輸出：

7

1、思路

首先我們先明白題目的意思，比如一個數(shù)組{7,5,6,4},它的逆序對總共有五對，{7,5},{7,6},{7,4},{5,4},{6,4} 只要是前面比后面大就組成一個逆序對。

看到這個題目，我們的第一反應是順序掃描整個數(shù)組。每掃描到一個數(shù)組的時候，逐個比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個數(shù)字就組成了一個逆序對。假設數(shù)組中含有n個數(shù)字。由于每個數(shù)字都要和O(n)這個數(shù)字比較，因此這個算法的時間復雜度為O(n^2)。

現(xiàn)在用上面說的這種方式是一種時間復雜度比較高的一種，我們換一種思路，采用歸并排序的方法。

先把數(shù)組分解成兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分解成兩個長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計逆序對的數(shù)目。在第一對長度為1的子數(shù)組{7}、{5}中7>5，因此（7,5）組成一個逆序對。同樣在第二對長度為1的子數(shù)組{6}，{4}中也有逆序對（6,4），由于已經(jīng)統(tǒng)計了這兩對子數(shù)組內(nèi)部的逆序對，因此需要把這兩對子數(shù)組進行排序，避免在之后的統(tǒng)計過程中重復統(tǒng)計。

逆序對的總數(shù) = 左邊數(shù)組中的逆序對的數(shù)量 + 右邊數(shù)組中逆序對的數(shù)量 + 左右結合成新的順序數(shù)組時中出現(xiàn)的逆序對的數(shù)量

2、編程實現(xiàn)

python

代碼實現(xiàn)方案：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if not data:
            return 0
        temp = [i for i in data]
        return self.mergeSort(temp, data, 0, len(data)-1) % 1000000007
    def mergeSort(self, temp, data, low, high):
        if low >= high:
            temp[low] = data[low]
            return 0
        mid = (low + high) / 2
        left = self.mergeSort(data, temp, low, mid)
        right = self.mergeSort(data, temp, mid+1, high)
        count = 0
        i = low
        j = mid+1
        index = low
        while i <= mid and j <= high:
            if data[i] <= data[j]:
                temp[index] = data[i]
                i += 1
            else:
                temp[index] = data[j]
                count += mid-i+1
                j += 1
            index += 1
        while i <= mid:
            temp[index] = data[i]
            i += 1
            index += 1
        while j <= high:
            temp[index] = data[j]
            j += 1
            index += 1
        return count + left + right

分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

審核編輯 黃昊宇