題目描述
在數(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ù)字
創(chuàng)新互聯(lián)公司長(zhǎng)期為上千多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為蘇尼特左企業(yè)提供專業(yè)的成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)，蘇尼特左網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
數(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
# -*- coding: utf-8 -*-
# @Time : 2019-07-12 11:39
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : inversePairs.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
要計(jì)算數(shù)組中的逆序?qū)Φ膶?duì)數(shù)，那么最直觀的做法就是遍歷整個(gè)數(shù)組，將當(dāng)前元素和后續(xù)的所有元素進(jìn)行
比較，然后累計(jì)有多少逆序?qū)Α?
另一種解法就是基于歸并排序的解法。
上述的解法的最大缺陷在于每個(gè)數(shù)字都要跟后續(xù)的所有數(shù)字進(jìn)行比較，導(dǎo)致時(shí)間復(fù)雜度為O(n^2)。
如果可以避免這么多次比較，就可以提高效率。
效仿歸并排序，我們先將一個(gè)數(shù)組不斷對(duì)半分裂，先得到多個(gè)長(zhǎng)度為1的數(shù)組，然后每?jī)蓚€(gè)相鄰數(shù)組進(jìn)行比較
然后歸并。
**之所以要進(jìn)行歸并(將這兩個(gè)相鄰數(shù)組合并后排序)是因?yàn)槿绻慌判虻脑?，在下一輪的比較的時(shí)候會(huì)出現(xiàn)
重復(fù)計(jì)數(shù)的情況**
由于進(jìn)行了排序，在下一輪歸并的時(shí)候只需要將兩個(gè)數(shù)組的最大值進(jìn)行比較，如果左邊的數(shù)組的最大值大于
右邊數(shù)組的最大值，那么說明右邊整個(gè)數(shù)組都可以跟左邊數(shù)組的最大值組成逆序?qū)Γ虼颂^左邊數(shù)組最大
值和右邊剩余元素的比較。
這種解法其實(shí)就是**降序的歸并排序**。
"""
def InversePairs(self, data):
def split(start, end):
# 先將整個(gè)數(shù)組對(duì)半分裂成若干個(gè)長(zhǎng)度為1的數(shù)組
if start < end: # start < end，說明長(zhǎng)度大于1，繼續(xù)分裂
mid = (start + end) >> 1
split(start, mid)
split(mid + 1, end)
# 分裂完成后，對(duì)兩個(gè)相鄰數(shù)組進(jìn)行歸并
# 兩個(gè)數(shù)組的下標(biāo)分別為[start, mid], [mid + 1, end]
merge(start, mid, end)
def merge(start, mid, end):
# 由于我們這里的count是InversePairs()里的局部變量，
# 所以用nonlocal關(guān)鍵字而非global
nonlocal count
# 由于是進(jìn)行降序歸并，因此從兩個(gè)數(shù)組的末尾開始?xì)w并
p1 = mid
p2 = end
while p1 >= start and p2 > mid:
# 如果左邊大于右邊，說明組成了一個(gè)逆序?qū)Γ? # 計(jì)數(shù)器count增加數(shù)值為右邊數(shù)組的剩余元素個(gè)數(shù)
if data[p1] > data[p2]:
# count += end - p2 + 1
count += p2 - mid
# data_copy用于存儲(chǔ)歸并后的結(jié)果
data_copy.append(data[p1])
p1 -= 1
else:
data_copy.append(data[p2])
p2 -= 1
# 將左右數(shù)組剩余的元素加入data_copy中，由于是有其中一個(gè)數(shù)組完全為空了，所以事實(shí)上
# 只將其中一個(gè)數(shù)組的元素加入data_copy中，而由于我們是利用遞歸實(shí)現(xiàn)的，這個(gè)數(shù)組也早
# 已有序，因此歸并后的結(jié)果data_copy是有序的
for p in range(p1, start - 1, -1):
data_copy.append(data[p])
for p in range(p2, mid, -1):
data_copy.append(data[p])
# 將歸并結(jié)果賦值到原數(shù)組中，注意這里賦值的順序，我們要保證從小到大。
while data_copy:
data[start] = data_copy.pop(-1)
start += 1
if not data:
return 0
count = 0 # 用于統(tǒng)計(jì)逆序?qū)Φ膶?duì)數(shù)
data_copy = [] # 輔助數(shù)組，用于存儲(chǔ)兩個(gè)相鄰數(shù)組歸并的臨時(shí)結(jié)果
split(0, len(data) - 1)
return count % 1000000007
def main():
solution = Solution()
data = [364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407, 416,
366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965, 516, 648,
727, 667, 465, 849, 455, 181, 486, 149, 588, 233, 144, 174, 557, 67,
746, 550, 474, 162, 268, 142, 463, 221, 882, 576, 604, 739, 288,
569, 256, 936, 275, 401, 497, 82, 935, 983, 583, 523, 697, 478, 147,
795, 380, 973, 958, 115, 773, 870, 259, 655, 446, 863, 735, 784, 3,
671, 433, 630, 425, 930, 64, 266, 235, 187, 284, 665, 874, 80, 45,
848, 38, 811, 267, 575]
# data = [1,2,3,4,5,6,7,0]
print(solution.InversePairs(data))
if __name__ == '__main__':
main()
