LeetCode算法日記 - Day 27: 計算右側小于當前元素的個數、翻轉對

1. 計算右側小于當前元素的個數

1.1 題目解析

1.2 解法

1.3 代碼實現

2. 翻轉對

2.1 題目解析

2.2 解法

2.3 代碼實現

1. 計算右側小于當前元素的個數

315. 計算右側小于當前元素的個數 - 力扣（LeetCode）

給你一個整數數組?nums?，按要求返回一個新數組?counts?。數組?counts?有該性質：?counts[i]?的值是??nums[i]?右側小于?nums[i]?的元素的數量。

示例 1：

輸入：nums = [5,2,6,1]
輸出：[2,1,1,0] 
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側僅有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側有 0 個更小的元素

示例 2：

輸入：nums = [-1]
輸出：[0]

示例 3：

輸入：nums = [-1,-1]
輸出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

1.1 題目解析

題目本質：

對每個位置 i，統計它右側有多少元素 < nums[i]。這是“離線統計 + 有序累積”的典型問題：如果能讓“右側區域”保持有序，那么當一個左側元素要“落位”時，就能一次性把比它小的右側元素數目加上去。
常規解法：對每個 i 向右掃一遍計數，或把每個 i 與其右邊所有元素比較。
復雜度 O(n2)，n 最多 1e5，超時。
問題分析：O(n2) 不行；要降低到 O(n log n)。要么用“平衡樹/樹狀數組/線段樹”邊插邊查，要么在“歸并排序”的有序合并過程中順手統計。
思路轉折：用 歸并排序（分治）。關鍵是不直接搬值，而是搬“原始下標”：
- 比較用 nums[index[*]]；
- 計數寫回 counts[index[*]]。
  這樣既能用數值排隊，又不丟原始位置，統計才能落對人。

1.2 解法

算法思想
維護一個下標數組 index，對下標做歸并：

????????降序歸并 + 一次性加法：左右兩段都保持降序。若 nums[left] > nums[right]，則右半段從 cur2 到 right 的所有元素都更小，直接 += (right - cur2 + 1) 并把左元素出列；否則先出右元素。

i）初始化：index[i]=i，counts 全 0，準備 tmp 臨時數組。

ii）分治：mergeSort(nums, left, right)。

iii）合并：

指針 cur1?=left, cur2 =mid+1，k 寫入 tmp。
若 nums[index[cur1]] <=?nums[index[cur2]]
tmp[k++]=index[cur2++]。
否則：counts[index[cur1]] += (right - j + 1)
tmp[k++]=index[cur1++]。
掃尾：
while (cur1 <= mid) tmp[k++] = index[cur1++];
while (cur2 <= right) tmp[k++] = index[cur2++];
回寫：
for (int j?= left; j?<= right; j++) index[j] = tmp[j?- left];

iiii）返回 counts 的列表形式。

易錯點

只搬下標，不搬值：比較寫 nums[index[*]]，統計寫 counts[index[*]]。
回寫的是 index，不是 nums：index[j]=tmp[j-left] 或讓 k 從 left 開始寫
注意 while 循環里比大小時判斷的條件
多層歸并要累加：counts[...] += ...，不能覆蓋。
tmp 不是答案數組，它只是合并時的 輔助排序區，是歸并用的臨時緩沖區，幫助我們把當前區間 [left..right] 合并成有序；排序這一步是必須的，因為我們借助“有序”的過程，才能在 O(n log n) 里順手統計“右邊更小”的個數。
counts：是真正的答案數組，counts[cur1] 表示 nums[cur1] 右側比它小的數量，最后返回它即可。
k++ 只是為了推進左半區的掃描，別忘了這個數組是記錄下標而不是原始數組的值，所以要推進下標數組的下標值。
index 數組的作用是“保持數值和原始下標之間的映射關系不丟失”。

1.3 代碼實現

import java.util.*;class Solution {int[] index;   // 記錄每個元素的“原始下標”，在歸并過程中只搬動下標int[] tmp;     // 臨時數組，用來輔助歸并排序（保存下標，不保存值）int[] counts;  // 結果數組，counts[i] = nums[i] 右側比它小的數量public List<Integer> countSmaller(int[] nums) {int n = nums.length;tmp = new int[n];counts = new int[n];index = new int[n];// 初始化下標數組，初始時 index[i] = ifor (int i = 0; i < n; i++) {index[i] = i;}// 分治歸并排序mergeSort(nums, 0, n - 1);// 把 counts 數組轉成 List<Integer> 返回List<Integer> list = new ArrayList<>(n);for (int v : counts) list.add(v);return list;}public 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);int cur1 = left, cur2 = mid + 1, k = 0;// 合并兩個有序區間（這里用“降序”方式）while (cur1 <= mid && cur2 <= right) {if (nums[index[cur1]] <= nums[index[cur2]]) {// 如果右邊的值更大或相等，先把右邊的下標放進 tmptmp[k++] = index[cur2++];} else {// 如果左邊的值更大：// 說明右邊 [cur2..right] 的元素全都比它小counts[index[cur1]] += (right - cur2 + 1);// 把這個左邊元素的下標放進 tmptmp[k++] = index[cur1++];}}// 把左半區剩余元素拷貝進 tmpwhile (cur1 <= mid) tmp[k++] = index[cur1++];// 把右半區剩余元素拷貝進 tmpwhile (cur2 <= right) tmp[k++] = index[cur2++];// 回寫：把 tmp 里的結果拷回到 index 數組對應區間for (int j = left; j <= right; j++) {index[j] = tmp[j - left];}}
}

復雜度分析

時間：分治 + 合并為 O(n log n)，每層合并線性。
空間：index/tmp/counts 為 O(n)，遞歸棧 O(log n)。

2. 翻轉對

493. 翻轉對 - 力扣（LeetCode）

給定一個數組?nums?，如果?i < j?且?nums[i] > 2*nums[j]?我們就將?(i, j)?稱作一個重要翻轉對。

你需要返回給定數組中的重要翻轉對的數量。

示例 1:

輸入: [1,3,2,3,1]
輸出: 2

示例 2:

輸入: [2,4,3,5,1]
輸出: 3

注意:

給定數組的長度不會超過50000。
輸入數組中的所有數字都在32位整數的表示范圍內。

2.1 題目解析

題目本質：統計所有滿足 i < j 且 nums[i] > 2 * nums[j] 的二元組數量。這是一個“離線統計 + 有序累積”的經典范式：如果左右兩段各自有序，就能用雙指針線性地數出跨段滿足條件的配對數量。
常規解法：雙重循環枚舉 (i, j)，逐對判斷是否 nums[i] > 2*nums[j]。時間復雜度 O(n^2)，n 最多可到 5e4，顯然超時。
問題分析：要把復雜度壓到 O(n log n)。兩條常見路徑：
1）平衡樹 / 樹狀數組 / 線段樹做“邊插邊查”；
2）分治歸并：在“合并”前用雙指針數跨段配對，再做標準歸并。
思路轉折：采用分治歸并。關鍵點：
- 先數對，后歸并：當左右段（[left..mid] 與 [mid+1..right]）各自已升序時，固定左段的 i，右段用 j 單調右移，線性統計滿足 nums[i] > 2*nums[j] 的個數。
- 用 long 比較避免溢出：：寫成 (long)nums[i] > 2L * (long)nums[j]，不要用 /2.0 的浮點比較。
- 歸并階段使用標準升序合并，保持下一層統計的前提（左右各自升序）。

2.2 解法

算法思想

分治：mergeSort(left, right)。在回溯（合并）前，借助“兩側各自升序”，對每個 i ∈ [left..mid]，移動 j 直到不滿足條件為止，累計 j - (mid + 1)。再做一次標準升序歸并，保證整體有序供更高層使用。

i）遞歸到底：left >= right 返回。

ii）遞歸左右：mergeSort(left, mid) 與 mergeSort(mid+1, right)。

iii）先統計：

j = mid + 1；
對每個 i = left..mid：while (j <= right && (long)nums[i] > 2L * (long)nums[j]) j++;
累加 result += (j - (mid + 1))。

iiii）再歸并（升序）：常規雙指針把 [left..mid] 與 [mid+1..right] 合并到 tmp，再回寫。

iiiii）返回最終 result。

易錯點

不要邊合并邊用 (right - cur2 + 1) 一把加：那是普通逆序對 nums[i] > nums[j] 的套路，對 > 2*nums[j] 不成立。
比較必須用 long：2 * nums[j] 在 int 里可能溢出。
不要用/2.0：浮點精度 + 負數邊界容易出錯，也不必要。
雙計數陷阱：要么用全局 result，要么函數返回值累計，二者不要混用。
合并要升序：保證下一層“先數對”的前提（左右各自已升序）。
指針單調：統計階段 j 只右移不回退，整體線性。

2.3 代碼實現

import java.util.*;class Solution {int[] tmp;int result;public int reversePairs(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return result;}// 只做副作用統計與排序，不用返回值累計public 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);// 先統計：左右兩段各自已升序int j = mid + 1;for (int i = left; i <= mid; i++) {while (j <= right && (long)nums[i] > 2L * (long)nums[j]) j++;// 右半段 [mid+1, j-1] 都滿足 nums[i] > 2*nums[?]result += (j - (mid + 1));}// 再歸并：標準升序合并int cur1 = left, cur2 = mid + 1, k = 0;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {tmp[k++] = nums[cur1++];} else {tmp[k++] = nums[cur2++];}}while (cur1 <= mid)  tmp[k++] = nums[cur1++];while (cur2 <= right) tmp[k++] = nums[cur2++];// 回寫for (int t = 0; t < k; t++) {nums[left + t] = tmp[t];}}
}

復雜度分析