LeetCode 1093. 大样本统计

2025-02-14 HGNULB 约 12 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1093. 大样本统计

题意分析

给定一个长度固定为 256 的数组 count，count[i] 表示整数 i 在样本中出现的次数（i 的取值就是 0 到 255）。要求返回五个统计量：最小值、最大值、平均数、中位数、众数，按这个顺序放进一个 double 数组。

题目已经把样本压缩成了频次表，这本身就是最大的提示：原始样本可能有 $10^9$ 个数，绝对不能展开成数组再排序；但它们只有 256 种取值，而且频次表天然按值升序排列——遍历下标 i 就等于按从小到大的顺序遍历样本。所有五个统计量都能在这个有序遍历中直接得出。

逐个拆解：最小值是第一个 count[i] > 0 的 i，最大值是最后一个；平均数是 Σ i × count[i] 除以总数；众数是 count[i] 最大的那个 i；中位数最麻烦，需要按累计频次定位第 ⌈total/2⌉ 与第 ⌊total/2⌋ + 1 个元素。

约束里有两处必须警惕。第一，count[i] 可以达到 $10^9$、总数也能到 $10^9$，所以 Σ i × count[i] 最大约 $255 \times 10^9 ≈ 2.55 \times 10^{11}$，远超 32 位整数范围，累加变量必须用 64 位。第二，题目保证样本非空且众数唯一，所以不必处理空样本和多众数的歧义。

边界：样本可能只有一种取值（此时最小值等于最大值等于中位数等于众数）；总数可能是偶数（中位数取中间两个数的平均，结果可能是 .5 结尾的小数）；count[0] > 0 时最小值是 0，用 -1 作「未初始化」哨兵才不会与合法值 0 混淆。

解法：一次统计

核心思路

暴力做法是把频次表展开成真正的样本数组，再排序、取首尾、求和、取中间。但总数可达 $10^9$，展开需要几 GB 内存，光是分配就不可行。瓶颈在于：样本被还原成了逐个元素，而频次表已经蕴含了排序结果，还原是纯粹的浪费。

换个视角：count 数组本身就是一个「按值升序、带重数」的有序序列。于是所有统计量都可以在对 256 个槽位的遍历中直接维护，与样本规模完全无关。

第一趟遍历同时维护四件事。最小值：遇到的第一个非零槽位，用 min == -1 判断是否已记录。最大值：每遇到一个非零槽位就覆盖 max，遍历结束后自然停在最后一个。总数与总和：total += count[i]、sum += (long) i * count[i]，平均数就是两者相除。众数：维护当前最大频次 modeCnt 与对应的值 mode，只在频次严格更大时更新；题目保证众数唯一，因此最终一定落在正确下标。

中位数需要第二趟。设总数为 total，把样本想象成从小到大排好的一列数（下标从 1 开始）。中位数是第 mid1 = (total + 1) / 2 个与第 mid2 = (total + 2) / 2 个元素的平均值——这个写法同时覆盖了奇偶两种情况：total 为奇数时两者相等（例如 total = 5 时都是 3），取平均等于取那一个；total 为偶数时两者相邻（例如 total = 4 时是 2 和 3），正好是中间两个。用一个公式吃掉奇偶讨论，比写 if (total % 2 == 0) 更短也更不易错。

定位的方法是维护累计频次 acc：从 i = 0 开始逐槽累加，第一次 acc >= mid1 时的 i 就是第 mid1 个元素的值（因为在此之前累计不足 mid1 个，说明第 mid1 个落在当前槽位里）；同理第一次 acc >= mid2 时的 i 就是第 mid2 个元素的值。由于 mid1 <= mid2，可以在同一趟里先后取到，取到 m2 就可以 break。

不变量：遍历到槽位 i 时，acc 恒等于样本中所有小于等于 i 的元素个数。 于是「第一次 acc >= k」等价于「第 k 小的元素恰好等于 i」。

正确性由频次表的有序性直接得到：第一个和最后一个非零下标分别是极值；Σ i × count[i] 对每个样本恰好求和一次；最大频次对应众数；累计频次跨过两个中间名次时得到的正是中位数的两个元素。五个统计量都没有依赖展开后的数组。

最后把五个量装进 double 数组返回。注意 min、max、mode 本身是整数，中位数与平均数才可能带小数。

解题步骤

min 与 max 初值取 -1 而不是 0 或 Integer.MAX_VALUE：样本值域是 [0, 255]，0 是合法值，用 0 当哨兵无法区分「还没遇到」与「最小值就是 0」；-1 落在值域之外，判断 min == -1 就能可靠地识别首次赋值。

只在 count[i] > 0 时更新统计量：频次为 0 的槽位代表这个值根本没出现，不能参与最小值、最大值的判定；对总和与总数虽然加 0 无害，但放在同一个分支里逻辑更清晰。

sum 必须用 64 位，且乘法前要先转型：Java 里写 sum += (long) i * count[i]，转型放在乘法之前——写成 (long) (i * count[i]) 时乘法已经在 int 域内溢出，转型救不回来。Go 明确使用 int64，不把正确性依赖在运行平台的 int 位宽上。

众数在频次严格增大时更新：遍历结束后，modeCnt 是目前见过的最大频次，mode 是取得该频次的值；题目保证众数唯一，无需另设并列规则。

中位数的两个位置用 (total + 1) / 2 与 (total + 2) / 2：整数除法自动向下取整，这两个表达式在奇偶两种情况下分别退化成「同一个位置」与「相邻两个位置」，无需分支。

m1 用 m1 == -1 保护只赋值一次：acc >= mid1 在之后的每一轮都成立，不加保护会一路覆盖到最后一个非零槽位。

求平均时把整型转成 double 再除：(double) sum / total 中的转型必须在除法之前，否则先做整数除法会丢掉小数部分。

中位数用 (m1 + m2) / 2.0：除数写成 2.0 而不是 2，否则又是整数除法。

以 count[1] = 4、count[2] = 1、count[3] = 3、count[4] = 2（其余为 0）走一遍。对应样本是 [1, 1, 1, 1, 2, 3, 3, 3, 4, 4]，众数唯一，正确答案为 [1.0, 4.0, 2.3, 2.5, 1.0]。

第一趟遍历：
i = 1：count[1] = 4 > 0，min 尚为 -1 故记 min = 1；max = 1；total = 4；sum = 1 × 4 = 4；4 > 0 故 modeCnt = 4、mode = 1。
i = 2：count[2] = 1 > 0，min 已定不动；max = 2；total = 5；sum = 4 + 2 = 6；1 > 4 不成立，众数不变。
i = 3：count[3] = 3 > 0；max = 3；total = 8；sum = 6 + 9 = 15；3 > 4 不成立，众数仍是 1。
i = 4：count[4] = 2 > 0；max = 4；total = 10；sum = 15 + 8 = 23；众数不变。
于是 min = 1、max = 4、total = 10、sum = 23，mean = 23 / 10 = 2.3，与直接对样本求和的结果一致。

第二趟求中位数：total = 10，mid1 = (10 + 1) / 2 = 5，mid2 = (10 + 2) / 2 = 6。
i = 0：acc = 0，两个条件都不满足。
i = 1：acc = 4，4 >= 5 不成立。
i = 2：acc = 5，5 >= 5 成立且 m1 == -1，记 m1 = 2；5 >= 6 不成立，继续。
i = 3：acc = 8，8 >= 6 成立，记 m2 = 3，break。
中位数 = (2 + 3) / 2.0 = 2.5。核对排好序的样本 [1, 1, 1, 1, 2, 3, 3, 3, 4, 4]，第 5 个是 2、第 6 个是 3，平均正是 2.5。

返回 [1.0, 4.0, 2.3, 2.5, 1.0]。

若把 m1 == -1 的保护条件去掉，i = 3 时会先把 m1 覆盖成 3，再设置 m2 = 3，中位数被误算为 3.0；第一次跨过 mid1 后必须锁定左中位数。

代码实现

// 中位数根据总数的中间位置，从小到大累计计数定位。
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];
                sum += (long) i * count[i];
                if (count[i] > modeCnt) {
                    modeCnt = count[i];
                    mode = i;
                }
            }
        }

        double mean = (double) sum / total;

        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)
			sum += int64(i) * int64(c)
			if c > modeCnt {
				modeCnt = c
				mode = i
			}
		}
	}

	mean := float64(sum) / float64(total)

	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 = count.length = 256。算法只扫描频次表两遍，与原始样本总数无关；在本题固定值域下也可视为 $O(1)$。

空间复杂度：$O(1)$，凭的是只用了十来个标量以及一个长度固定为 5 的返回数组，没有任何随样本规模增长的结构。

关键点总结

看到「样本被压缩成频次表」，第一反应就是不要还原样本：频次表已经是按值有序的表示，所有顺序统计量（最小、最大、中位数、分位数）都能靠累计频次直接定位，复杂度与样本规模无关。

「第 k 小」的通用定位方法是累计频次 + 首次达标：维护 acc 表示「小于等于当前值的元素个数」，第一次 acc >= k 时的值就是第 k 小。这个技巧在桶排序、值域二分、可持久化线段树里反复出现。

中位数的奇偶讨论可以用 (total + 1) / 2 与 (total + 2) / 2 一次吃掉，两个位置在奇数时重合、偶数时相邻，取平均即可。记住这一对表达式能省掉一个容易写错的分支。

哨兵值必须落在合法值域之外：本题值域含 0，所以 min 的初值只能用 -1 而不能用 0。选哨兵前先问一句「这个值会不会是合法答案」。

溢出是本题最实际的坑：Σ i × count[i] 可达 $2.55 \times 10^{11}$，必须用 64 位，且转型要放在乘法之前。

面试视角：这道题看起来是「送分的模拟题」，但面试官真正在看的是你有没有注意到溢出、哨兵、奇偶合并这三处细节。答完后可以主动提一句：如果频次表要支持动态更新并随时查询中位数，就该换成树状数组上二分，或者用对顶堆（295 题的做法）。

易错点总结

错误写法：sum 用 int 累加：count[255] = 10^9 → 255 × 10^9 远超 int 上限，溢出成负数，平均数变成负值，正确答案是 255.0。

错误写法：转型写成 sum += (long) (i * count[i])：count[255] = 10^9 → 乘法已经在 int 域内溢出，转型只是把错误的负数扩宽，结果依旧错误。转型必须写在乘法的操作数上。

错误写法：min 初值设为 0：count[5] = 1（只有一个样本 5）→ min 从未被识别为「未赋值」，返回 0，正确答案是 5.0。

错误写法：min 初值设为 Integer.MAX_VALUE 却仍用 min == -1 判断首次赋值：任意输入 → 条件永不成立，min 保持 MAX_VALUE，返回一个巨大的数。哨兵值与判断条件必须配套。

错误写法：m1 的赋值不加 m1 == -1 保护：count[1] = 4、count[2] = 1、count[3] = 3、count[4] = 2 → m1 在定位 m2 的同一轮被覆盖成 3，中位数算成 3.0，正确答案是 2.5。

错误写法：中位数写成 (m1 + m2) / 2：同上输入 → 整数除法把 (2 + 3) / 2 算成 2，返回 2.0，正确答案是 2.5。

错误写法：平均数写成 (double) (sum / total)：count[1] = 1、count[2] = 1 → 先做整数除法得 3 / 2 = 1，返回 1.0，正确答案是 1.5。转型必须在除法之前。

错误写法：中位数位置写成 total / 2 与 total / 2 + 1：total = 5（奇数）→ 两个位置变成 2 和 3，取的是第 2 与第 3 个元素的平均，而正确的中位数是第 3 个元素本身；样本 [1, 1, 2, 3, 3] 会算成 1.5，正确答案是 2.0。

错误写法：最大值只在 count[i] > count[max] 时更新：count[1] = 5、count[9] = 1 → 把「频次最大」误当成「值最大」，返回 max = 1，正确答案是 9.0。最大值只看是否出现过，与出现次数无关。

错误写法：先把频次表展开成样本数组再排序求中位数：total = 10^9 → 需要约 4 GB 内存，直接内存溢出；即便勉强分配，排序也要 $O(n \log n)$ 完全超时。

相似题目

题目	难度	考察点
295. 数据流的中位数	困难	值域不受限、数据持续到来，无法用频次表，需要对顶堆动态维护中位数
面试题 17.20. 连续中值	困难	与 295 同题，可用来检验对顶堆两侧规模的平衡条件是否写熟
480. 滑动窗口中位数	困难	中位数要随窗口滑动而增删元素，对顶堆还需支持延迟删除或改用有序表
4. 寻找两个正序数组的中位数	困难	同样是求第 k 小，但靠对分割点二分做到 $O(\log(m+n))$，不能累计计数
169. 多数元素	简单	只求众数且保证过半，可用摩尔投票做到 $O(1)$ 空间，不必建频次表
347. 前 K 个高频元素	中等	由频次表求前 k 大频次，需要堆或桶排序，考的是「按频次排序」而非「按值定位」
1122. 数组的相对排序	简单	同样利用小值域的计数数组代替排序，是本题「频次表即有序表示」思想的另一种应用