豆包 315.计算右侧小于当前元素的个数 public List＜Integer＞ countSmaller(int[] nums)

我直接给你能直接提交 LeetCode 的 Java 题解，这是 315. Count of Smaller Numbers After Self 最优解法：归并排序 + 索引数组，时间复杂度 O(n log n)。

完整代码

java

import java.util.*;

class Solution {
private int[] index; // 记录原始下标
private int[] temp; // 归并临时数组
private int[] res; // 答案

public List<Integer> countSmaller(int[] nums) { int n = nums.length; index = new int[n]; temp = new int[n]; res = new int[n]; for (int i = 0; i < n; i++) { index[i] = i; } mergeSort(nums, 0, n - 1); List<Integer> ans = new ArrayList<>(); for (int num : res) { ans.add(num); } return ans; } // 归并排序 private void mergeSort(int[] nums, int l, int r) { if (l >= r) return; int mid = (l + r) >>> 1; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); merge(nums, l, mid, r); } // 合并并统计右侧比它小的数 private void merge(int[] nums, int l, int mid, int r) { int i = l, j = mid + 1; int pos = l; while (i <= mid && j <= r) { if (nums[index[i]] <= nums[index[j]]) { temp[pos++] = index[i]; res[index[i]] += j - (mid + 1); i++; } else { temp[pos++] = index[j++]; } } // 处理左边剩余 while (i <= mid) { temp[pos++] = index[i]; res[index[i]] += j - (mid + 1); i++; } // 处理右边剩余 while (j <= r) { temp[pos++] = index[j++]; } // 复制回去 System.arraycopy(temp, l, index, l, r - l + 1); }

}

思路一句话

• 用归并排序对数组从右往左合并
• 合并时，右边已经有序，可以直接算出有多少个数比当前数小
• 用 index[] 保存原始下标，保证答案能对应回原位置

如果你愿意，我可以再给你：

• 树状数组（Fenwick Tree）版本
• 线段树版本
• 逐行注释极简版

你想要哪个？