劍指Offer（35）：數組中的逆序對

一、引子

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

二、題目

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數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

1、思路

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

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

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

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

逆序對的總數 = 左邊數組中的逆序對的數量 + 右邊數組中逆序對的數量 + 左右結合成新的順序數組時中出現的逆序對的數量

2、編程實現

python

代碼實現方案：

# -*- 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”系列資訊類文章，歡迎您的關注！

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇