「@Author：Runsen」
逆序數，我在很多的面試題都見過，本質上來說難度是比較大，因為如果使用暴力法當資料量一大，必然就會爆掉。你現在就要記住逆序數就是考歸并排序。
逆序數
給定一個數組array[0,...,n-1], 若對于某兩個元素array[i],array[j],若i<j and array[i]>array[j],
則認為array[i],array[j]是逆序對。一個數組中包含的逆序對的數目稱為該數組的逆序數。設計一個算法求一個數組的逆序數
比如給出數組
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]]
複制
歸并排序
「下面說下歸并排序的思路。」 我們可以在歸并排序的基礎上, 完成對逆序對的個數統計.
歸并排序的過程:
- 将數組拆分成左右兩個部分
- 對左邊進行歸并排序
- 對右邊進行歸并排序
- 合并左右兩邊
我們可以發現一點, 完成第三步操作之後，并不會改變這樣的逆序對(一個數在左邊，另一個數在右邊)的個數.
是以逆序對統計的過程為:
- 将數組拆分成左右兩個部分
- 對左邊進行歸并排序,并傳回左邊的逆序對個數leftCount 。比如，11和8是一個，3和9不是，繼續，8和3是一個，8和9不是一個，11和3是一個，11和9也是一個，是以leftCount = 4
- 對右邊進行歸并排序,并傳回右邊的逆序對個數rightCount=3 。
- 合并左右兩邊,并計算這樣的逆序對(一個數在左邊，另一個數在右邊)個數crossCount 14.
- 數組的逆序對個數為: leftCount + rightCount + crossCount = 21.
利用歸并排序計算逆序數對的方法太巧妙了，但是隻要提醒你一下使用分治思想，或者使用歸并排序思想解決這道問題你可能就有思路了。歸并排序實際上會把數組分成兩個有序部分，我們不妨稱其為左和右，歸并排序的過程中會将左右兩部分合并成一個有序的部分，對于每一個左右部分，我們分别計算其逆序數，然後全部加起來就是我們要求的逆序數，詳細的思路在代碼中注釋了。
'''
@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] < nums[j]:
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. 數組中的逆序對
比如[3，4，1，5，2]
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
具體代碼和上面代碼差不多，下面代碼來源Leetcode官網。
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。
參考資料
[1]傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -