Hard
493. Reverse Pairs
arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set
解題說明
Reverse Pairs
題目描述:給定一個整數陣列 nums,計算「重要逆序對」的數量。重要逆序對定義為 i < j 且 nums[i] > 2 * nums[j]。
解題思路:利用歸併排序的分治策略。在合併兩個已排序的子陣列之前,先用雙指標計算跨越左右半段的重要逆序對數量。由於左右兩半已各自排序,對於左半段的每個元素 nums[i],右半段中滿足 nums[i] > 2 * nums[j] 的 j 形成一個前綴,且隨 i 增大此前綴只會增長(單調性)。因此雙指標掃描的總時間為 O(n)。加上歸併排序本身的 O(n log n),總時間為 O(n log n)。
C++ 解法
複雜度分析
時間複雜度:O(n log n) — 歸併排序的分治結構,每層合併和計數均為 O(n),共 O(log n) 層。
空間複雜度:O(n) — 歸併排序所需的暫存空間。
虛擬碼
1. Define mergeSort(nums, lo, hi):
a. Base case: if lo >= hi, return 0
b. mid = (lo + hi) / 2
c. count = mergeSort(nums, lo, mid) + mergeSort(nums, mid+1, hi)
d. Count cross pairs with two pointers:
- j = mid + 1
- For each i in [lo, mid]:
- While j <= hi and nums[i] > 2 * nums[j]: j++
- count += j - (mid + 1)
e. Merge nums[lo..mid] and nums[mid+1..hi]
f. Return count
2. Return mergeSort(nums, 0, n-1)其他解法
BIT + 離散化 O(n log n):將所有值和其二倍值離散化。從右到左遍歷,對每個 nums[i],在 BIT 中查詢小於 nums[i]/2 的元素數量(即之前插入的 j > i 中 nums[j] < nums[i]/2 的個數),然後將 nums[i] 插入 BIT。
BST / 平衡樹 O(n log n):使用平衡二元搜尋樹(如 AVL 或紅黑樹),從右到左遍歷,每次查詢小於 nums[i]/2 的節點數量後插入 nums[i]。但 C++ STL 的 set/map 不直接支援 order statistics,需要使用 policy-based tree 或手寫。
延伸思考
- 如果條件改為 nums[i] > k * nums[j](k 為任意常數),方法是否仍然適用?
- 這個問題與經典的逆序對計數(i < j 且 nums[i] > nums[j])有何異同?
- 能否用 CDQ 分治(陳丹琦分治)來解決此問題?