LCR 170. 交易逆序對的總數 - 力扣（LeetCode）

在股票交易中，如果前一天的股價高于后一天的股價，則可以認為存在一個「交易逆序對」。請設計一個程序，輸入一段時間內的股票交易記錄?record，返回其中存在的「交易逆序對」總數。

示例 1：

輸入：record = [9, 7, 5, 4, 6]
輸出：8
解釋：交易中的逆序對為 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

提示：

0 <= record.length <= 50000

暴力解法的問題

最直觀的解法是雙重循環遍歷所有可能的?(i, j)?組合，統計滿足?i < j?且?record[i] > record[j]?的對數。這種方法的時間復雜度為 O(n2)，當數組長度較大（例如 50000）時，顯然無法高效處理。

歸并排序解法

歸并排序的分治思想天然適合解決逆序對問題。在歸并排序的合并階段，可以高效地統計逆序對數目。

歸并排序合并階段的統計邏輯

1. ?分治：將數組分為左右兩部分，遞歸處理左右子數組。
2. ?合并：合并兩個有序子數組時，若左子數組的當前元素大于右子數組的當前元素，則左子數組中剩余的所有元素均與該右子數組元素構成逆序對。
3. ?累加：每次發現左子數組元素大于右子數組元素時，累加左子數組剩余元素的個數到總逆序對數目。

代碼實現

class Solution {int[] tmp; // 臨時數組用于歸并排序int ret;   // 統計逆序對總數public int reversePairs(int[] nums) {tmp = new int[nums.length];mergesort(nums, 0, nums.length - 1);return ret;}private void mergesort(int[] nums, int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;// 遞歸處理左右子數組mergesort(nums, left, mid);mergesort(nums, mid + 1, right);// 若左子數組最大值 <= 右子數組最小值，無需合并if (nums[mid] <= nums[mid + 1]) return;// 合并兩個有序子數組，并統計逆序對int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {tmp[i++] = nums[cur1++];} else {ret += mid - cur1 + 1; // 統計逆序對數目tmp[i++] = nums[cur2++];}}// 處理剩余元素while (cur1 <= mid) tmp[i++] = nums[cur1++];while (cur2 <= right) tmp[i++] = nums[cur2++];// 將排序后的臨時數組復制回原數組for (int j = left; j <= right; j++) {nums[j] = tmp[j - left];}}
}

示例分析

以示例?record = [9, 7, 5, 4, 6]?為例，歸并排序的合并過程如下：

1. ?初始分割：數組分為左?[9,7,5]?和右?[4,6]。
2. ?處理左子數組：
   • 分割為?[9,7]?和?[5]，合并時?9 > 7?產生 1 個逆序對。
   • 合并?[7,9]?和?[5]，7 > 5?產生 2 個逆序對。
3. ?處理右子數組：合并?[4]?和?[6]，無逆序對。
4. ?合并左右子數組：
   • 比較?5?和?4，產生 3 個逆序對。
   • 比較?5?和?6，無逆序對。
   • 比較?7?和?6，產生 2 個逆序對。
   • 累計總逆序對數目為 1 + 2 + 3 + 2 = 8。

復雜度分析

• ?時間復雜度：O(n log n)，歸并排序的時間復雜度。
• ?空間復雜度：O(n)，用于歸并排序的臨時數組。

通過歸并排序的分治策略，可以在高效排序的同時統計逆序對數目，從而快速解決大規模數據的逆序對問題。