面試題51. 數組中的逆序對 題目來源： "https://leetcode cn.com/problems/shu zu zhong de ni xu dui lcof/" 題目 在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的 ...
面試題51. 數組中的逆序對
題目來源：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
題目
在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。
示例 1:
輸入: [7,5,6,4]
輸出: 5
解題思路
思路：歸併排序
歸併排序使用了分治的思想，這個過程需要使用遞歸來實現。在分治演算法遞歸實現中，每層遞歸會涉及三個步驟：
- 分解：將原問題分解為一系列子問題；
- 解決：遞歸求解各個子問題，若子問題足夠小，直接求解；
- 合併：將子問題的結果合併為原問題。
在本題當中，
- 分解：假設區間為
[left, right]，令mid = [(left + right) / 2]，將[left, right]分成[left, mid]和[mid + 1, right]； - 解決：使用遞歸排序兩個子序列；
- 合併：將已經排好的子序列
[left, mid]和[mid + 1, right]合併
題目中要求返回數組構成逆序對的總數。逆序對：即是前面的一個數字大於後面的數字，那麼這兩個數字可以構成一個逆序對。
具體思想參考代碼。
代碼實現
class Solution:
def reversePairs(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
# 輔助數組，用於歸併
temp = [0] * n
return self.count_invs(nums, 0, n - 1, temp)
def count_invs(self, nums, left, right, temp):
if left == right:
return 0
mid = (left + right) // 2
left_pairs = self.count_invs(nums, left, mid, temp)
right_pairs = self.count_invs(nums, mid+1, right, temp)
# 這裡表示已經排序好，並且已經計算左右兩部分未排序前的逆序對
invs_pairs = left_pairs + right_pairs
if nums[mid] < nums[mid + 1]:
# 這個時候表示都是順序排序，不用計算兩個區間交叉的逆序對，直接返回
return invs_pairs
# 這裡計算區間交叉的逆序對
invs_cross_pairs = self.merge_count(nums, left, mid, right, temp)
return invs_pairs + invs_cross_pairs
def merge_count(self, nums, left, mid, right, temp):
# 現在兩個區間都是有序的
# 合併計算此時區間交叉的逆序對個數
# 複製原數組到輔助數組
for i in range(left, right + 1):
temp[i] = nums[i]
p = left
q = mid + 1
ans = 0
for i in range(left, right + 1):
# 這裡歸併剩餘的部分
if p > mid:
nums[i] = temp[q]
q += 1
elif q > right:
nums[i] = temp[p]
p += 1
elif temp[p] <= temp[q]:
# 這個時候，前面部分區間的元素出列
# 因為 p 對應的元素，比 q 對應的元素小
# 那麼 p 對應的元素一定比 q 對應元素後面的元素都小
# 所以這個時候不統計逆序對，p 往前移動
nums[i] = temp[p]
p += 1
else:
# 這種屬於相反的情況
# p 對應的元素比 q 對應的元素大，
# 那麼 p 對應的元素後面的元素一定更大
# 所以，元素出列同時統計逆序對
# 這個時候，數組位置 p 到該區間末尾有多少個元素就有多少個逆序對，即是 mid - p + 1
nums[i] = temp[q]
q += 1
ans += (mid - p + 1)
return ans
實現結果
以上就是使用歸併排序的思想，解決《面試題51. 數組中的逆序對》問題的主要內容。
歡迎關註微信公眾號《書所集錄》
