LeetCode 1365. 有多少小于当前数字的数字
目录
题目描述
题意分析
给定数组
nums，对每个下标i统计数组中有多少个j（$j \ne i$）满足nums[j] < nums[i]，把所有答案按原下标顺序组成数组返回。
题面里有两个词必须抠死。一是「小于」，是严格小于，等于当前数字的元素不能计入；二是「$j \ne i$」，看似要求排除自己，但因为比较是严格小于、而
nums[i] < nums[i]恒为假，自己本来就不会被数进去，所以这个条件其实不需要任何额外处理——这一点值得在面试里主动说出来，说明你读懂了题而不是照抄条件。
约束是本题唯一的算法信号：$1 \le n \le 500$，$0 \le nums[i] \le 100$。数组长度小到 $O(n^2)$ 都能过，但值域被死死限制在 0 到 100 这 101 个整数上，这是一个非常刺眼的提示：值域比数组长度还小，说明可以用值域直接开桶，而不是去排序或用哈希表。凡是「值域是小常数」的题，第一反应都应该是计数数组。
还要注意返回的是按原下标排列的答案数组，不是排序后的数组。所以任何打乱原顺序的做法（比如原地排序
nums）都必须想清楚怎么把答案映射回原位置。
边界有三处。数组只有一个元素时，答案是
[0]。所有元素相同时，因为是严格小于，答案全是0。值0是合法输入，且没有任何数小于它，所以0对应的答案恒为0——这一点决定了前缀数组的初始项必须是 0。
解法：计数数组 + 前缀和
核心思路
暴力做法是两层循环：对每个
i扫一遍整个数组，数出比它小的元素个数。$n \le 500$ 时这个 $O(n^2)$ 的做法完全能过，写法也没有陷阱。但它的浪费很明显：如果nums[i] == nums[k]，那么它们的答案必然相同，暴力却把同一次统计重复做了两遍。换句话说，答案只是「值」的函数，与下标无关，而值最多只有 101 种。
顺着这个观察走：真正要求的是一个函数 $g(v)$ = 数组中严格小于 $v$ 的元素个数，然后把每个
nums[i]拿去查表就行。而 $g$ 显然可以由频次累加得到——先统计每个值出现了几次，再对频次求前缀和。
于是定义两个数组。
freq[v]表示值v在nums中出现的次数，$v \in [0, 100]$。prefix[v]表示nums中严格小于v的元素个数，也就是 $\sum_{u < v} freq[u]$。
这两个定义之间的递推关系是
prefix[v] = prefix[v - 1] + freq[v - 1]，边界是prefix[0] = 0。这条递推最容易写错的地方在于右边加的是freq[v - 1]而不是freq[v]：prefix[v]要的是「小于 v」，所以它等于「小于 v-1 的个数」加上「恰好等于 v-1 的个数」。如果误写成prefix[v] = prefix[v-1] + freq[v]，得到的就是「小于等于 v」的语义，相等的元素会被错误地计入。这个「严格小于 / 小于等于」的错位就是本题最核心的考点。
prefix[0] = 0这个初值同时承担了两个含义：没有任何整数小于 0（因为值域下界就是 0），以及前缀和递推需要一个空前缀作为起点。它天然由数组的零值初始化提供，不需要额外写。
最后一步，按原下标顺序遍历
nums，answer[i] = prefix[nums[i]]。因为prefix是按值索引的，查表是 $O(1)$，且原数组的顺序完全没有被破坏，返回的答案自动就是题目要的下标顺序。
作为对照，另一条常见思路是「排序后回填」：把
nums拷贝一份排序，然后对每个值找它在有序数组中第一次出现的下标，那个下标就是小于它的元素个数。这个做法是 $O(n \log n)$，且必须用「第一次出现」而不是任意出现位置，否则重复值会算错。值域这么小的时候，计数 + 前缀和更简单也更快，是这题的标准答案。
解题步骤
- 开一个长度 101 的频次数组：下标范围要覆盖
[0, 100]全闭区间，所以长度是 101 而不是 100。少开一格会在遇到值 100 时直接数组越界。
- 一次遍历统计频次：
freq[num]++。这一步不关心下标，只关心值，是「答案只依赖值」这个观察的直接体现。
- 开一个长度 101 的前缀数组并递推：
for (int i = 1; i <= 100; i++) prefix[i] = prefix[i - 1] + freq[i - 1];。循环必须从 1 开始，因为prefix[0]是不需要计算的边界（恒为 0），从 0 开始会访问prefix[-1]。上界写<= 100是因为值 100 也可能出现在nums里，它需要一个有效的查询结果。
- 注意这一步和「值是否真的出现过」无关：即使某个值一次都没出现，
prefix在那个位置也会被正确填成「小于它的元素个数」。前缀数组是对整个值域填满的，不是只对出现过的值填。
- 按原顺序查表生成答案：
answer[i] = prefix[nums[i]]。这里绝不能对nums做任何重排，否则下标对应关系就断了。
以
nums = [8, 1, 2, 2, 3]走一遍（正确答案[4, 0, 1, 1, 3]）。
第一遍统计频次：
freq[1] = 1、freq[2] = 2、freq[3] = 1、freq[8] = 1，其余全为 0。
第二遍递推前缀。
prefix[0] = 0。prefix[1] = prefix[0] + freq[0] = 0 + 0 = 0（没有元素小于 1）。prefix[2] = prefix[1] + freq[1] = 0 + 1 = 1（只有那个 1）。prefix[3] = prefix[2] + freq[2] = 1 + 2 = 3（1 和两个 2）。prefix[4] = prefix[3] + freq[3] = 3 + 1 = 4。prefix[5]到prefix[8]因为freq[4]到freq[7]全是 0，一路保持 4。
第三遍查表：
nums[0] = 8 → prefix[8] = 4；nums[1] = 1 → prefix[1] = 0；nums[2] = 2 → prefix[2] = 1；nums[3] = 2 → prefix[2] = 1；nums[4] = 3 → prefix[3] = 3。拼起来是[4, 0, 1, 1, 3]，与答案一致。
特别看下标 2 和 3 这两个都等于 2 的元素：它们查的是同一格
prefix[2]，自然得到相同的答案 1，而且这个 1 里不包含另一个 2——因为prefix[2]的定义是严格小于 2。如果递推误写成prefix[i] = prefix[i-1] + freq[i]，prefix[2]会变成0 + 2 = 2，两个 2 各自把对方（以及自己）算了进去，输出变成[4, 1, 2, 2, 4]，五个位置里错了四个。
代码实现
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
// 值域是 [0, 100] 闭区间，长度必须是 101。
int[] freq = new int[101];
for (int num : nums) {
freq[num]++;
}
// prefix[v] 表示严格小于 v 的元素个数，prefix[0] = 0 由零值初始化天然成立。
int[] prefix = new int[101];
for (int i = 1; i <= 100; i++) {
// 加的是 freq[i - 1] 而不是 freq[i]，否则语义会滑成「小于等于 i」。
prefix[i] = prefix[i - 1] + freq[i - 1];
}
// 按原下标顺序查表，不能重排 nums，否则答案与位置的对应关系就断了。
int[] answer = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[nums[i]];
}
return answer;
}
}
func smallerNumbersThanCurrent(nums []int) []int {
// 值域是 [0, 100] 闭区间，长度必须是 101。
freq := make([]int, 101)
for _, num := range nums {
freq[num]++
}
// prefix[v] 表示严格小于 v 的元素个数，prefix[0] = 0 由零值初始化天然成立。
prefix := make([]int, 101)
for i := 1; i <= 100; i++ {
// 加的是 freq[i-1] 而不是 freq[i]，否则语义会滑成「小于等于 i」。
prefix[i] = prefix[i-1] + freq[i-1]
}
// 按原下标顺序查表，不能重排 nums，否则答案与位置的对应关系就断了。
answer := make([]int, len(nums))
for i, num := range nums {
answer[i] = prefix[num]
}
return answer
}
复杂度分析
- 时间复杂度：$O(n + C)$，其中 $n$ 是数组长度、$C = 101$ 是值域大小。统计频次和查表各扫一遍数组共 $O(n)$，递推前缀和扫一遍值域 $O(C)$。相比排序法的 $O(n \log n)$，它是线性的，代价是必须知道值域上界。
- 空间复杂度：$O(C)$，两个长度 101 的辅助数组，与输入规模无关；结果数组是题目要求的输出，通常不计入额外空间。如果想省一半，可以只用一个数组做原地前缀和（先统计频次再就地累加，但要注意此时数组语义已变），本题没有必要。
关键点总结
- 看到「值域是个小常数」（这里是 0 到 100）就该联想到计数数组：用值当下标开桶，可以把很多 $O(n \log n)$ 或 $O(n^2)$ 的统计降到 $O(n + C)$。这是计数排序家族的共同入口。
- 「答案只依赖值、不依赖下标」是本题从暴力走向优化的关键观察。凡是发现相同输入被重复计算，就应该考虑把结果按「输入的取值」缓存下来。
- 前缀和的语义边界必须写死在纸上：这里
prefix[v]是严格小于v，所以递推里加的是freq[v - 1]。「小于」和「小于等于」的一格之差是这类题最高频的错误来源，写代码前先把定义念一遍。
- 值域数组要按闭区间长度开（
[0, 100]对应 101 格），并且要为值域内所有取值填好前缀，而不是只填出现过的值——否则查询未出现的值时会拿到脏数据。
- 面试里可以把三种做法排成一条线来答：$O(n^2)$ 暴力 → $O(n \log n)$ 排序找首次出现位置 → $O(n + C)$ 计数前缀和，并说明第三种成立的前提是值域有界。能主动指出「$j \ne i$ 这个条件因为是严格小于所以不需要额外处理」通常也是加分项。
易错点总结
- 递推写成
prefix[i] = prefix[i - 1] + freq[i]：语义变成「小于等于 i」。nums = [8,1,2,2,3]会输出[4,1,2,2,4]而不是[4,0,1,1,3]，每个值都把与自己相等的元素（含自己）算了进去。
- 频次数组只开 100 格：
nums中出现 100 时freq[100]++直接数组越界，而这个值完全合法。
- 前缀循环从
i = 0开始：prefix[0] = prefix[-1] + freq[-1]直接越界；prefix[0]本来就该是 0，不需要参与递推。
- 前缀循环上界写成
i < 100：prefix[100]永远是 0，输入里任何等于 100 的元素答案都会是 0。例如nums = [100, 1]会输出[0, 0]，正确答案是[1, 0]。
- 为了排序方便直接对
nums原地排序再回填：原下标信息被破坏，nums = [8,1,2,2,3]排完变成[1,2,2,3,8]，即使算对了也无法还原成题目要求的下标顺序。
- 用排序法时取「值在有序数组中的任意出现位置」而非首次出现位置：
[1,2,2,3]中第二个 2 的下标是 2，会得到答案 2，而正确答案是 1，重复值全部偏大。
- 误以为要显式排除
j == i而把答案减一：因为比较是严格小于，自己从来没被计入，减一会让所有非最小元素的答案偏小 1。
- 把答案数组写成
new int[101]而不是new int[nums.length]：返回的数组长度与输入不符，判题直接失败。
- 用哈希表代替计数数组但忘了未出现的值：查询
map.get(v)时若v没出现过会拿到null触发空指针，用计数数组则天然是 0。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1122. 数组的相对排序 | 简单 | 同样靠值域开桶，但输出是重排后的数组，且顺序由第二个数组指定 |
| LCR 075. 数组的相对排序 | 简单 | 与 1122 同题，可直接套用同一份计数桶写法 |
| 1636. 按照频率将数组升序排序 | 简单 | 计数之后不是求前缀，而是把频次当作排序的主关键字 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 只统计右侧且值域很大，静态前缀和失效，需要树状数组或归并排序在线维护 |
| 912. 排序数组 | 中等 | 值域有界时计数排序 $O(n + C)$ 优于比较排序，本题正是它的统计阶段 |
| 338. 比特位计数 | 简单 | 同样是「按值域填满一张表、用前一项推当前项」的递推填表套路 |
| 274. H 指数 | 中等 | 值被 n 截断后开桶，但求的是后缀和（统计不小于 h 的个数），方向相反 |