八十二、歸并排序求取復(fù)雜的逆序數(shù)

「@Author：Runsen」

逆序數(shù)，我在很多的面試題都見過，本質(zhì)上來說難度是比較大，因為如果使用暴力法當數(shù)據(jù)量一大，必然就會爆掉。你現(xiàn)在就要記住逆序數(shù)就是考歸并排序。

逆序數(shù)

給定一個數(shù)組array[0,...,n-1], 若對于某兩個元素array[i],array[j],若iarray[j],

則認為array[i],array[j]是逆序?qū)?。一個數(shù)組中包含的逆序?qū)Φ臄?shù)目稱為該數(shù)組的逆序數(shù)。設(shè)計一個算法求一個數(shù)組的逆序數(shù)

比如給出數(shù)組nums = [11, 8, 3, 9, 7, 1, 2, 5]，我可以求出[(11, 8), (8, 3), (11, 3), (11, 9), (7, 1), (7, 2), (7, 5), (3, 1), (8, 1), (9, 1), (11, 1), (3, 2), (8, 2), (9, 2), (11, 2), (8, 5), (9, 5), (11, 5), (8, 7), (9, 7), (11, 7)]

采用暴力破解的話，代碼非常簡單。

r?=?[]
def?reversePairs(nums):
????size?=?len(nums)
????if?size?2:
????????return?0
????res?=?0
????for?i?in?range(0,?size?-?1):
????????for?j?in?range(i?+?1,?size):
????????????if?nums[i]?>?nums[j]:
????????????????res?+=?1
????????????????r.append([nums[i],nums[j]])
????return?res

print(reversePairs([11,?8,?3,?9,?7,?1,?2,?5]))
print(r)

21
[[11,?8],?[11,?3],?[11,?9],?[11,?7],?[11,?1],?[11,?2],?[11,?5],?[8,?3],?[8,?7],?[8,?1],?[8,?2],?[8,?5],?[3,?1],?[3,?2],?[9,?7],?[9,?1],?[9,?2],?[9,?5],?[7,?1],?[7,?2],?[7,?5]]

歸并排序

「下面說下歸并排序的思路?！?/strong> 我們可以在歸并排序的基礎(chǔ)上, 完成對逆序?qū)Φ膫€數(shù)統(tǒng)計.

歸并排序的過程:

• 將數(shù)組拆分成左右兩個部分
• 對左邊進行歸并排序
• 對右邊進行歸并排序
• 合并左右兩邊

我們可以發(fā)現(xiàn)一點, 完成第三步操作之后，并不會改變這樣的逆序?qū)?一個數(shù)在左邊，另一個數(shù)在右邊)的個數(shù).

因此逆序?qū)y(tǒng)計的過程為:

• 將數(shù)組拆分成左右兩個部分
• 對左邊進行歸并排序,并返回左邊的逆序?qū)€數(shù)leftCount 。比如，11和8是一個，3和9不是，繼續(xù)，8和3是一個，8和9不是一個，11和3是一個，11和9也是一個，因此leftCount = 4
• 對右邊進行歸并排序,并返回右邊的逆序?qū)€數(shù)rightCount=3 。
• 合并左右兩邊,并計算這樣的逆序?qū)?一個數(shù)在左邊，另一個數(shù)在右邊)個數(shù)crossCount 14.
• 數(shù)組的逆序?qū)€數(shù)為: leftCount + rightCount + crossCount = 21.

利用歸并排序計算逆序數(shù)對的方法太巧妙了，但是只要提醒你一下使用分治思想，或者使用歸并排序思想解決這道問題你可能就有思路了。歸并排序?qū)嶋H上會把數(shù)組分成兩個有序部分，我們不妨稱其為左和右，歸并排序的過程中會將左右兩部分合并成一個有序的部分，對于每一個左右部分，我們分別計算其逆序數(shù)，然后全部加起來就是我們要求的逆序數(shù)，詳細的思路在代碼中注釋了。

'''
@Author：Runsen
@WeChat：RunsenLiu 
@微信公眾號：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/25
'''
temp?=?[0]?*?100
count?=?[0]
pairs?=?[]

def?Merge(nums,?low,?mid,?high):
????i?=?low
????j?=?mid?+?1
????size?=?0
????while?i?<=?mid?and?j?<=?high:
????????if?nums[i]?????????????temp[size]?=?nums[i]
????????????i?+=?1
????????else:
????????????#?除了以下三行代碼，其余代碼與歸并排序一模一樣
????????????count[0]?+=?(mid?-?i?+?1)
????????????for?h?in?range(i,?mid?+?1):
????????????????pairs.append((nums[h],?nums[j]))
????????????temp[size]?=?nums[j]
????????????j?+=?1
????????size?+=?1
????while?i?<=?mid:
????????temp[size]?=?nums[i]
????????size?+=?1
????????i?+=?1
????while?j?<=?high:
????????temp[size]?=?nums[j]
????????size?+=?1
????????j?+=?1
????for?i?in?range(size):
????????nums[low?+?i]?=?temp[i]


def?Merge_sort(nums,?low,?high):
????if?low?>=?high:
????????return
????mid?=?(low?+?high)?>>?1
????Merge_sort(nums,?low,?mid)
????Merge_sort(nums,?mid?+?1,?high)
????#?此時是排好序
????Merge(nums,?low,?mid,?high)


if?__name__?==?'__main__':
????nums?=?[11,?8,?3,?9,?7,?1,?2,?5]
????Merge_sort(nums,?0,?len(nums)?-?1)
????print(pairs)
????print(count)

[(11,?8),?(8,?3),?(11,?3),?(11,?9),?(7,?1),?(7,?2),?(7,?5),?(3,?1),?(8,?1),?(9,?1),?(11,?1),?(3,?2),?(8,?2),?(9,?2),?(11,?2),?(8,?5),?(9,?5),?(11,?5),?(8,?7),?(9,?7),?(11,?7)]
[21]

該題對標的是Leetcode：劍指 Offer 51. 數(shù)組中的逆序?qū)?/p>

比如[3，4，1，5，2]

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

具體代碼和上面代碼差不多，下面代碼來源Leetcode官網(wǎng)。

class?Solution:
????def?reversePairs(self,?nums:?List[int])?->?int:
????????self.cnt?=?0
????????def?merge(nums,?start,?mid,?end):
????????????i,?j,?temp?=?start,?mid?+?1,?[]
????????????while?i?<=?mid?and?j?<=?end:
????????????????if?nums[i]?<=?nums[j]:
????????????????????temp.append(nums[i])
????????????????????i?+=?1
????????????????else:
????????????????????self.cnt?+=?mid?-?i?+?1
????????????????????temp.append(nums[j])
????????????????????j?+=?1
????????????while?i?<=?mid:
????????????????temp.append(nums[i])
????????????????i?+=?1
????????????while?j?<=?end:
????????????????temp.append(nums[j])
????????????????j?+=?1
????????????
????????????for?i?in?range(len(temp)):
????????????????nums[start?+?i]?=?temp[i]
????????????????????

????????def?mergeSort(nums,?start,?end):
????????????if?start?>=?end:?return
????????????mid?=?(start?+?end)?>>?1
????????????mergeSort(nums,?start,?mid)
????????????mergeSort(nums,?mid?+?1,?end)
????????????merge(nums,?start,?mid,??end)
????????mergeSort(nums,?0,?len(nums)?-?1)
????????return?self.cnt

好了，今天的分享就到這了！

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

參考資料