LeetCode 1365. 有多少小于当前数字的数字
题目描述
题意分析
对每个
nums[i]，统计整个数组中严格小于它的元素个数，并将结果放在答案的相同下标处。统计的是出现次数，不是不同数字的种类数；相等的元素不计入。
解法：计数数组 + 前缀和
核心思路
[!blue]
如果对每个位置重新扫描全数组，会重复比较相同的数值。题目中所有数都在 $[0,100]$ 内，可以先用
freq[v]记录值 $v$ 在整个数组中出现多少次，同一个值的答案便只需计算一次。定义
prefix[v]为严格小于 $v$ 的元素总数。因为输入没有负数，prefix[0] = 0；从 $v-1$ 到 $v$，新增的较小元素只有值恰好为 $v-1$ 的那些，所以prefix[v] = prefix[v - 1] + freq[v - 1]。按值从小到大递推，就能得到所有查询结果。最后仍按原数组下标遍历，令
answer[i] = prefix[nums[i]]。每个更小元素都按其频次计入，相等元素全部被排除；自身也不可能严格小于自身，因此不需要再减一。查表不会改变输入顺序，相同值自然得到相同答案。
解题步骤
- 建立101格频次数组。
- 从一到一百求排除自身值的前缀数量。
- 按原下标查表生成答案。
代码实现
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] freq = new int[101];
for (int num : nums) {
freq[num]++;
}
int[] prefix = new int[101];
for (int i = 1; i <= 100; i++) {
// 只累计到前一个值，保证不包含与当前值相等的元素。
prefix[i] = prefix[i - 1] + freq[i - 1];
}
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 {
freq := make([]int, 101)
for _, num := range nums {
freq[num]++
}
prefix := make([]int, 101)
for i := 1; i <= 100; i++ {
// 只累计到前一个值，保证不包含与当前值相等的元素。
prefix[i] = prefix[i-1] + freq[i-1]
}
answer := make([]int, len(nums))
for i, num := range nums {
// 按原下标查值域统计，重复值自然有相同答案。
answer[i] = prefix[num]
}
return answer
}
复杂度分析
- 时间复杂度：$O(n+101)$，统计频次与生成答案各遍历一次数组，前缀统计遍历固定值域。
- 空间复杂度：$O(101)$ 辅助空间，输出另占 $O(n)$。
关键点总结
[!green]
- 严格小于已经自动排除自身，无需再减一。
- 零的答案为零，一百也必须有可查询的表项。
易错点总结
[!yellow]
- 递推加当前频次会改变边界语义。
- 数组只开一百格，合法值一百会越界。
- 直接排序输入后按新位置返回，会丢掉原下标对应关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 在排序副本中寻找每个值的下界，下界下标就是严格较小元素的数量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！