劍指Offer（三十五）：數(shù)組中的逆序?qū)?/h1>
搜索微信公眾號:'AI-ming3526'或者'計(jì)算機(jī)視覺這件小事' 獲取更多算法、機(jī)器學(xué)習(xí)干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners
一、引子
搜索微信公眾號:'AI-ming3526'或者'計(jì)算機(jī)視覺這件小事' 獲取更多算法、機(jī)器學(xué)習(xí)干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners
這個系列是我在牛客網(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。
查看完整的劍指Offer算法題解析請點(diǎn)擊CSDN和github鏈接：
劍指Offer完整習(xí)題解析CSDN地址
github地址
二、題目
在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出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},它的逆序?qū)偣灿形鍖?，{7,5},{7,6},{7,4},{5,4},{6,4} 只要是前面比后面大就組成一個逆序?qū)Α?/p>
看到這個題目，我們的第一反應(yīng)是順序掃描整個數(shù)組。每掃描到一個數(shù)組的時候，逐個比較該數(shù)字和它后面的數(shù)字的大小。如果后面的數(shù)字比它小，則這兩個數(shù)字就組成了一個逆序?qū)?。假設(shè)數(shù)組中含有n個數(shù)字。由于每個數(shù)字都要和O(n)這個數(shù)字比較，因此這個算法的時間復(fù)雜度為O(n^2)。
現(xiàn)在用上面說的這種方式是一種時間復(fù)雜度比較高的一種，我們換一種思路，采用歸并排序的方法。
先把數(shù)組分解成兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分解成兩個長度為1的子數(shù)組。接下來一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對長度為1的子數(shù)組{7}、{5}中7>5，因此（7,5）組成一個逆序?qū)?。同樣在第二對長度為1的子數(shù)組{6}，{4}中也有逆序?qū)Γ?,4），由于已經(jīng)統(tǒng)計(jì)了這兩對子數(shù)組內(nèi)部的逆序?qū)Γ虼诵枰堰@兩對子數(shù)組進(jìn)行排序，避免在之后的統(tǒng)計(jì)過程中重復(fù)統(tǒng)計(jì)。
逆序?qū)Φ目倲?shù) = 左邊數(shù)組中的逆序?qū)Φ臄?shù)量 + 右邊數(shù)組中逆序?qū)Φ臄?shù)量 + 左右結(jié)合成新的順序數(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
AIMI-CN AI學(xué)習(xí)交流群【1015286623】 獲取更多AI資料
分享技術(shù)，樂享生活：我們的公眾號計(jì)算機(jī)視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
