493. Reverse Pairs

解題說明

C++ 解法

複雜度分析

虛擬碼

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)

其他解法

延伸思考