LeetCode 1093. 大样本统计
题目描述
题意分析
样本中的整数都在零到二百五十五之间，输入
count[i]表示数值i出现了多少次。按照最小值、最大值、平均数、中位数、众数的顺序，返回五个浮点统计量。输入是频次表，数组下标才是样本值，数组元素是出现次数。样本总数至少为一，众数保证唯一。中位数按所有样本排序后的位置确定，平均数按全部出现加权计算，不能把不同值简单平均，也不应把巨大样本重新展开。
解法：两趟频次统计
核心思路
[!blue]
按下标从小到大扫描频次表。第一个频次非零的下标就是最小值，最后一个频次非零的下标就是最大值；频次最大的下标是众数，注意返回的是对应数值，而不是这个最大频次。
每个数值
i为总数量贡献count[i]，为总和贡献i * count[i]。分别累计为total和sum，平均数就是sum / total。加权总和可能超过 32 位整数，乘法前就要将操作数提升为 64 位，不能等乘法溢出后再转换。做除法时也要先转换为浮点数，保留小数部分。中位数不用真的排序展开。采用一基名次，统一取
(total + 1) / 2和(total + 2) / 2，这里是整数除法。总数为奇数时，两者都是同一个中间名次；总数为偶数时，它们就是相邻的两个中间名次，最后求两个对应值的平均数。第二次按数值递增累加频次。若某个值之前累计了
before个样本，它的频次为c，那么排序后第before + 1到第before + c个位置都是这个值。累计数量第一次达到某个目标名次时，当前下标就是该名次的值，即使一次越过多个位置也不需要逐个展开。左中位值只在第一次达到左名次时保存，不能继续覆盖；右名次达到时即可结束扫描。两个目标名次也可能落在同一频次段中，此时两个中位值相同，同样用平均公式处理。零是合法样本值，因此未赋值状态使用值域外的
-1。
解题步骤
- 第一遍扫描非零频次，确定最小值、最大值、众数，并累计总数和加权总和。
- 用浮点除法计算平均数，再确定两个中间名次。
- 第二遍从小到大累计频次，分别记录第一次覆盖这两个名次的样本值。
- 求两个中间值的浮点平均数，按题目指定顺序返回五项。
代码实现
class Solution {
public double[] sampleStats(int[] count) {
int min = -1;
int max = -1;
int mode = 0;
long total = 0;
long sum = 0;
int modeCnt = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
if (min == -1) {
min = i;
}
max = i;
total += count[i];
// 先提升到 64 位再乘频次，防止整数乘法溢出。
sum += (long) i * count[i];
if (count[i] > modeCnt) {
modeCnt = count[i];
mode = i;
}
}
}
double mean = (double) sum / total;
// 两个名次统一处理奇偶总数，名次从 1 开始。
long mid1 = (total + 1) / 2;
long mid2 = (total + 2) / 2;
int m1 = -1;
int m2 = -1;
long acc = 0;
for (int i = 0; i < count.length; i++) {
acc += count[i];
// 只记录第一次跨过左中位数名次的值。
if (acc >= mid1 && m1 == -1) {
m1 = i;
}
if (acc >= mid2) {
m2 = i;
break;
}
}
double median = (m1 + m2) / 2.0;
return new double[] {
min,
max,
mean,
median,
mode
};
}
}
func sampleStats(count []int) []float64 {
minVal := -1
maxVal := -1
mode := 0
var total int64
var sum int64
modeCnt := 0
for i, c := range count {
if c > 0 {
if minVal == -1 {
minVal = i
}
maxVal = i
total += int64(c)
// 先提升到 64 位再乘频次，防止整数乘法溢出。
sum += int64(i) * int64(c)
if c > modeCnt {
modeCnt = c
mode = i
}
}
}
mean := float64(sum) / float64(total)
// 两个名次统一处理奇偶总数，名次从 1 开始。
mid1 := (total + 1) / 2
mid2 := (total + 2) / 2
var acc int64
m1, m2 := -1, -1
for i, c := range count {
acc += int64(c)
// 只记录第一次跨过左中位数名次的值。
if acc >= mid1 && m1 == -1 {
m1 = i
}
if acc >= mid2 {
m2 = i
break
}
}
median := float64(m1+m2) / 2.0
return []float64{
float64(minVal),
float64(maxVal),
mean,
median,
float64(mode),
}
}
复杂度分析
- 时间复杂度：$O(C)$，
C为频次表长度，两次扫描都只处理表项，不依赖展开后的样本总数；本题C = 256，为固定规模。- 空间复杂度：$O(1)$，只保存固定数量的统计变量和五项返回结果。
关键点总结
[!green]
- 频次表同时给出数值顺序和重复数量，可以直接计算所有统计量。
- 加权求和使用数值乘次数，中间排名用累计次数定位。
- 两个中间名次统一处理奇偶，极值与中位值的未赋值状态不能占用合法样本零。
易错点总结
[!yellow]
- 将
count[i]当作样本值，会混淆数据与它的次数。- 先做 32 位乘法再转成 64 位，总和加入之前的乘积就可能已经溢出。
- 先做整数除法再转浮点，平均数的小数部分已经丢失；中位数也应使用浮点除法。
- 每次累计频次超过左名次都覆盖左中位值，会把它错误移动到更大的数值。
- 用是否恰好等于目标名次来寻找中位数，会漏掉一次频次累加跨过名次的情况；应判断大于等于。
- 将众数返回为最高出现次数，或者按五项的错误顺序组装结果，都不符合输出约定。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 347. 前 K 个高频元素 | 中等 | 频次最大者是众数，本题还需结合频次和数值计算平均数、中位数等统计量。 |