What is the time complexity of the 'Statistics from a Large Sample' problem?

The time complexity typically depends on the approach used for median calculation, but a good approach runs in O(n), where n is the length of the count array (256).

How can I calculate the median in this problem?

The median is found by either selecting the middle element directly if the sample size is odd or averaging the two middle elements if the sample size is even.

How should I handle large input sizes for this problem?

Focus on optimizing both time and space complexity. Ensure that your solution handles the large input sizes without excessive memory usage or slow execution times.

What is the most common mistake in this problem?

The most common mistake is miscalculating the median, especially for even-sized samples, or failing to properly sum the elements for the mean.

How do I find the mode in this problem?

The mode is the most frequent number in the sample. Traverse the `count` array and identify the index with the highest value, which corresponds to the mode.

#1093

Medium

auto_awesome数组·数学

LeetCode 题解工作台

大样本统计

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中： count[k] 就是整数 k 在样本中出现的次数。计算以下统计数据: minimum ：样本中的最小元素。 maximum ：样品中的最大元素。 mean ：样本的平均值，计算为所有元素的总和除以元素总数。 med…

数组数学概率与统计

题目描述

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。

计算以下统计数据:

minimum ：样本中的最小元素。
maximum ：样品中的最大元素。
mean ：样本的平均值，计算为所有元素的总和除以元素总数。
median ：
- 如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
- 如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
mode ：样本中出现次数最多的数字。保众数是唯一的。

以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10^-5 内的答案都可以通过。

示例 1：

输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
解释：用count表示的样本为[1,2,2,2,3,3,3,3]。
最小值和最大值分别为1和3。
均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。
因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。
众数为3，因为它在样本中出现的次数最多。

示例 2：

输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,4.00000,2.18182,2.00000,1.00000]
解释：用count表示的样本为[1,1,1,1,2,2,3,3,3,4,4]。
最小值为1，最大值为4。
平均数是(1+1+1+1+2+2+2+3+3+4+4)/ 11 = 24 / 11 = 2.18181818…(为了显示，输出显示了整数2.18182)。
因为样本的大小是奇数，所以中值是中间元素2。
众数为1，因为它在样本中出现的次数最多。

提示：

count.length == 256
0 <= count[i] <= 10⁹
1 <= sum(count) <= 10⁹
count 的众数是唯一的

lightbulb

解题思路

方法一：模拟

我们直接根据题目描述模拟即可，定义以下变量：

变量 $mi$ 表示最小值；
变量 $mx$ 表示最大值；
变量 $s$ 表示总和；
变量 $cnt$ 表示总个数；
变量 $mode$ 表示众数。

我们遍历数组 $count$ ，对于当前遍历到的数字 $count[k]$ ，如果 $count[k] \gt 0$ ，那么我们做以下更新操作：

更新 $mi = \min(mi, k)$ ；
更新 $mx = \max(mx, k)$ ；
更新 $s = s + k \times count[k]$ ；
更新 $cnt = cnt + count[k]$ ；
如果 $count[k] \gt count[mode]$ ，那么更新 $mode = k$ 。

遍历结束后，我们再根据 $cnt$ 的奇偶性来计算中位数 $median$ ，如果 $cnt$ 是奇数，那么中位数就是第 $\lfloor \frac{cnt}{2} \rfloor + 1$ 个数字，如果 $cnt$ 是偶数，那么中位数就是第 $\lfloor \frac{cnt}{2} \rfloor$ 和第 $\lfloor \frac{cnt}{2} \rfloor + 1$ 个数字的平均值。

这里我们通过一个简单的辅助函数 $find(i)$ 来找到第 $i$ 个数字，具体实现可以参考下面的代码。

最后，我们将 $mi, mx, \frac{s}{cnt}, median, mode$ 放入答案数组中返回即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $count$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        def find(i: int) -> int:
            t = 0
            for k, x in enumerate(count):
                t += x
                if t >= i:
                    return k

        mi, mx = inf, -1
        s = cnt = 0
        mode = 0
        for k, x in enumerate(count):
            if x:
                mi = min(mi, k)
                mx = max(mx, k)
                s += k * x
                cnt += x
                if x > count[mode]:
                    mode = k

        median = (
            find(cnt // 2 + 1) if cnt & 1 else (find(cnt // 2) + find(cnt // 2 + 1)) / 2
        )
        return [mi, mx, s / cnt, median, mode]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently compute the median from a large sample?
question_mark
Does the candidate handle large inputs and edge cases correctly?
question_mark
Is the solution optimized for both time and space complexity?

warning

常见陷阱

外企场景

error
Miscalculating the median by not properly handling both odd and even sample sizes.
error
Forgetting to properly sum the elements in the count array to calculate the mean.
error
Mistaking the mode for another statistic (e.g., assuming it's the maximum value instead of the most frequent).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling edge cases like a sample with only one unique value or a very small sample size.
arrow_right_alt
Modifying the problem to calculate only a subset of the statistics, e.g., just the mean and mode.
arrow_right_alt
Optimizing for large-scale datasets where memory and time efficiency become critical.

help

常见问题

外企场景

继续练习

#1467 两个盒子中球的颜色数相同的概率 #1073 负二进制数相加 #1131 绝对值表达式的最大值