大样本统计

难度: Medium

我们对 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 的众数是唯一的

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        n=sum(count)
        s=0
        max_v,min_v=-inf,inf
        t=0
        mode,m=0,0
        a,b=None,None
        for i,v in enumerate(count):
            if v>m:
                m=v
                mode=i
            t+=i*v
            if i>max_v and v>0:
                max_v=i
            if i<min_v and v>0:
                min_v=i
            s+=v
            if v>0 and s>=n//2 and a is None:
                a=i
            if v>0 and s>=n//2+1 and b is None:
                b=i
        if n&1:
            mean=b
        else:
            mean=(a+b)/2
        return [min_v,max_v,t/n,mean,mode]

Explain

题解通过一次遍历数组 count，计算最小值、最大值、平均值、中位数和众数。最小值和最大值通过检查每个数字的计数是否大于零并更新最小或最大索引来得到。平均值通过累加所有数字乘以其出现次数再除以总数计算。中位数通过累积出现的次数直到达到或超过总数的一半来确定。如果总元素数是奇数，中位数是累计到的那个数；如果是偶数，则取累积到的两个数的平均值。众数是出现次数最多的数字。

时间复杂度: O(256) => O(1)

空间复杂度: O(1)

# 增加注释的题解代码
class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        n = sum(count) # 总元素数
        s = 0
        max_v, min_v = -inf, inf # 初始化最大最小值
        t = 0 # 总和
        mode, m = 0, 0 # 众数及其频率
        a, b = None, None # 用于计算中位数
        for i, v in enumerate(count):
            if v > m: # 找出众数
                m = v
                mode = i
            t += i * v # 累计总和
            if i > max_v and v > 0: # 更新最大值
                max_v = i
            if i < min_v and v > 0: # 更新最小值
                min_v = i
            s += v
            if v > 0 and s >= n // 2 and a is None: # 找第一个中位数
                a = i
            if v > 0 and s >= n // 2 + 1 and b is None: # 找第二个中位数
                b = i
        mean = (a + b) / 2 if n % 2 == 0 else b # 计算中位数
        return [float(min_v), float(max_v), t / n, float(mean), float(mode)] # 返回结果

Explore

在count数组中，每个索引代表一个数字，而该索引的值代表该数字出现的次数。为了确定最小值，从count数组的开始遍历，找到第一个计数大于0的索引，这个索引即为最小值。同样，为了找到最大值，从count数组的末尾向前遍历，直到找到第一个计数大于0的索引，这个索引即为最大值。这种方法确保了即便数组中有大量的0计数（即某些数值未出现），也能准确找到出现过的最小和最大数值。

是的，当处理非常大的数据集时，计算平均值前累加总和可能导致整数溢出。为了避免这个问题，可以采用更大范围的数据类型（如Python中的长整型），或者逐步计算平均值来减小每一步的数值范围，比如使用在线算法进行平均值的更新。在Python中，整数通常会自动转换为长整型以避免溢出，但在其他语言中，如C++或Java，需要显式使用长整型数据类型来处理大数的累加。

计算中位数时，如果元素总数n为偶数，中位数是第n/2个元素和第n/2+1个元素的平均值。当累积频率恰好等于n/2时，表示第n/2个元素已经包括在内，因此这个元素应当是中位数的一部分。然后继续遍历直到找到下一个非零频率的元素，这个元素则是第n/2+1个元素。取这两个元素的值的平均，即为最终的中位数。如果累积频率直接跳过了n/2而没有等于的情况，则中位数可能刚好是一个具体的值，而不需要平均。

在这个题解中，众数的定义是出现频率最高的单一数字。如果有多个数字具有相同的最高频率，题解中的实现只记录了首次遇到的那个数字。这种选择是基于简化实现的考虑。然而，如果需要考虑所有具有最高频率的数字，应该修改算法来收集所有这些数字，而不只是第一个遇到的。这通常涉及使用一个列表或其他数据结构来存储所有频率最高的数字，并在最后返回所有这些数字。