劍指Offer（35）：數(shù)組中的逆序?qū)?/h1>

一、引子

這個(gè)系列是我在牛客網(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。
查看完整的劍指Offer算法題解析請(qǐng)點(diǎn)擊CSDN和github鏈接：
劍指Offer完整習(xí)題解析CSDN地址
github地址

二、題目

在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007

輸入描述：

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

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

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

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

事例1：

輸入：

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

輸出：

7

1、思路

首先我們先明白題目的意思，比如一個(gè)數(shù)組{7,5,6,4},它的逆序?qū)偣灿形鍖?duì)，{7,5},{7,6},{7,4},{5,4},{6,4} 只要是前面比后面大就組成一個(gè)逆序?qū)Α?/p>

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

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

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

逆序?qū)Φ目倲?shù) = 左邊數(shù)組中的逆序?qū)Φ臄?shù)量 + 右邊數(shù)組中逆序?qū)Φ臄?shù)量 + 左右結(jié)合成新的順序數(shù)組時(shí)中出現(xiàn)的逆序?qū)Φ臄?shù)量

2、編程實(shí)現(xiàn)

python

代碼實(shí)現(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

分享技術(shù)，樂享生活：我們的公眾號(hào)計(jì)算機(jī)視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！

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

審核編輯 黃昊宇