劍指Offer（三十五）：陣列中的逆序對
搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners
一、引子
這個系列是我在牛客網上刷《劍指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
AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料
分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/72028.html
標籤：其他
上一篇：救救孩子吧