目錄

1. 歸并排序

1.1 題目解析

1.2 解法

1.3 代碼實現

2. 交易逆序對的總數

2.1 題目解析

2.2 解法

2.3 代碼實現

---

1. 歸并排序

912. 排序數組 - 力扣（LeetCode）

給你一個整數數組?nums，請你將該數組升序排列。

你必須在?不使用任何內置函數?的情況下解決問題，時間復雜度為?O(nlog(n))，并且空間復雜度盡可能小。

示例 1：

輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]
解釋：數組排序后，某些數字的位置沒有改變（例如，2 和 3），而其他數字的位置發生了改變（例如，1 和 5）。

示例 2：

輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]
解釋：請注意，nums 的值不一定唯一。

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

1.1 題目解析

題目本質

把整數數組 nums 升序排列。目標是在不調用內置排序的前提下，做到 O(n log n) 的時間復雜度，且額外空間盡量小。

常規解法

• 直接用冒泡 / 插入 / 選擇：實現簡單，但時間復雜度 O(n^2)，在 n=5*10^4 時會超時。

• 快排（手寫）：平均 O(n log n)，最壞 O(n^2)，實現要注意樞軸與不變式，否則容易退化。

問題分析

題目希望穩定達成 O(n log n)。穩定、可控且好實現的選擇是歸并排序：

• 分而治之（遞歸二分）保證 log n 層；

• 每層合并代價 O(n)；

• 總體 O(n log n)；

• 代價是需要一段臨時數組 tmp（O(n) 額外空間）。

思路轉折

要想時間穩定在 O(n log n) 且實現穩健 → 走歸并排序路線：

• 先把左右兩段分別排好；

• 合并時雙指針線性掃一遍，把更小的元素依次寫入 tmp；

• 最后把 tmp 回寫到 nums[left..right]。

預測：時間 O(n log n)；空間 O(n)（單份 tmp 復用，已經是歸并常見的最小開銷版）。

1.2 解法

算法思想

分治 + 合并?對區間 [left, right]：

1. 劃分中點 mid = (right + left) / 2；

2. 遞歸排好 [left, mid] 與 [mid+1, right]；

3. 用雙指針 cur1、cur2 合并到 tmp[0..]；

4. 把 tmp 覆蓋回 nums[left..right]。

此實現是穩定排序：當相等時 nums[cur1] <= nums[cur2] 先取左邊，保持相對次序。

i）在 sortArray 中創建一份長度為 nums.length 的 tmp，供所有遞歸復用；

ii）mergeSort(nums, left, right)：?

• 遞歸終止：left >= right；

• 分治：mergeSort(nums, left, mid) 與 mergeSort(nums, mid+1, right)；

• 合并：

  • cur1 = left, cur2 = mid+1, i = 0；

  • 當 cur1<=mid && cur2<=right：把較小的放入 tmp[i++]；

  • 掃尾：把剩余的另一側元素依次放入 tmp；

  • 回寫：for (int j = left; j <= right; j++) nums[j] = tmp[j-left];

易錯點

• 合并時比較的是元素值：nums[cur1] <= nums[cur2]，不是下標范圍。

• 遞增 i 指針?tmp[i++] 。

• 回寫時的偏移要用 j - left，因為 tmp 從 0 寫起。

1.3 代碼實現

class Solution {int[] tmp;public int[] sortArray(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;    }public void mergeSort(int[] nums, int left, int right) {if (left >= right) {return;}int mid = (right + left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);int i = 0, cur1 = left, cur2 = mid + 1;while (cur1 <= mid && cur2 <= right) {tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : 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];}}
}

復雜度分析

• 時間復雜度：O(n log n)

• 空間復雜度：O(n)

2. 交易逆序對的總數

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

2.1 題目解析

題目本質

這是典型的逆序對計數：給定數組 record，統計滿足 i < j 且 record[i] > record[j] 的有序對數量。

核心抽象：用分治 + 合并（歸并排序），在合并兩段有序區間時批量統計跨段逆序對。

常規解法

雙重循環枚舉所有 (i, j)，判斷 record[i] > record[j]。

問題分析

暴力是 O(n^2)，n=5e4 時約 12.5 億次比較，不可接受。

思路轉折

要高效 → 需要在有序結構里批量計數 → 歸并合并時一次比較可累計一段：

• 升序合并：若 nums[i] > nums[j]（i∈[left,mid], j∈[mid+1,right]），則左側 [i..mid] 全部大于 nums[j]，一次性加 mid - i + 1。

• 降序合并：若 nums[i] > nums[j]，則右側 [j..right] 全部小于 nums[i]，一次性加 right - j + 1。

預測：整體 O(n log n)，可過最大規模。

2.2 解法

算法思想

分治 + 合并計數?對 [left, right]：

• 遞歸統計左區間 [left, mid] 總數、右區間 [mid+1, right] 總數；

• 合并時統計跨跨區間總數

• 總數 ret = 左區間 + 右區間??+ 跨區間。

升序合并公式

nums[i] > nums[j] ? ret += (mid - i + 1)。

降序合并公式

nums[i] > nums[j] ? ret += (right - j + 1)。

兩種寫法都對；差別只在“誰先入 tmp ”以及“加哪一側的剩余長度”。

i）遞歸把 [left, right] 拆到長度為 1；

ii）分別統計左右段的逆序對；

iii）合并兩段有序數組，同時批量統計跨段逆序對；

iiii）回寫 tmp 到 nums[left..right]；

iiiii）返回計數。

易錯點

• 遞歸區間錯誤

• 合并時比較的是“值”，不是下標范圍：if (nums[i] <= nums[j])。

• 遞增臨時數組指針：tmp[k++]

• 計數的“參照物”要和合并方向匹配：

  • 升序合并：右更小時加左側剩余 mid - i + 1。

  • 降序合并：左更大時加右側剩余 right - j + 1。

• 回寫用偏移：nums[j] = tmp[j-left]，不要用已移動過的 left 做下標。j 遍歷原區間 [left..right]，j-left 就是對應的 tmp 下標。

2.3 代碼實現

方法一：升序合并計數

class Solution {int dest;         int[] tmp;public int reversePairs(int[] record) {if (record == null || record.length < 2) return 0;dest = 0;                                  tmp = new int[record.length];int result = mergeSort(record, 0, record.length - 1);return result;}public int mergeSort(int[] nums, int left, int right) {if (left >= right) return 0;int mid = left + (right - left) / 2;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {     // 升序合并if (nums[cur1] <= nums[cur2]) {tmp[i++] = nums[cur1++];} else {// 右更小 → 左側 [cur1..mid] 都 > nums[cur2]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];}return ret;}
}

方法二：降序合并計數

class Solution {int dest;          int[] tmp;public int reversePairs(int[] record) {if (record == null || record.length < 2) return 0;dest = 0;tmp = new int[record.length];int result = mergeSort(record, 0, record.length - 1);return result;}public int mergeSort(int[] nums, int left, int right) {if (left >= right) return 0;int mid = left + (right - left) / 2;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {     // 降序合并if (nums[cur1] > nums[cur2]) {// 左更大 → 右側 [cur2..right] 都 < nums[cur1]ret += (right - cur2 + 1);tmp[i++] = nums[cur1++];} else {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];}return ret;}
}

復雜度分析

• 時間復雜度：O(n log n)

• 空間復雜度：O(n)