跳转至

LeetCode: 1093. 大样本统计

1、题目描述

我们对 0255 之间的整数进行采样,并将结果存储在数组 count 中:count[k] 就是整数 k 的采样个数。

我们以 浮点数 数组的形式,分别返回样本的最小值、最大值、平均值、中位数和众数。其中,众数是保证唯一的。

我们先来回顾一下中位数的知识:

  • 如果样本中的元素有序,并且元素数量为奇数时,中位数为最中间的那个元素;
  • 如果样本中的元素有序,并且元素数量为偶数时,中位数为中间的两个元素的平均值。

示例 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]

示例 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.length == 256
  • 1 <= sum(count) <= 10^9
  • 计数表示的众数是唯一的
  • 答案与真实值误差在 10^-5 以内就会被视为正确答案

2、解题思路

  • 从前向后扫描一遍即可
  • 中位数需要注意,判断总数的奇偶性
class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        total_count = sum(count)
        temp_min = 255
        temp_max = 0
        average_sum = 0
        most = 0

        mid_num = [-1, -1]
        current_count = 0
        for index, c in enumerate(count):
            if c:
                temp_min = min(temp_min, index)
                temp_max = max(temp_max, index)
                mid_count = total_count // 2
                if total_count % 2:
                    if mid_num[0] == -1 and current_count + c >= mid_count + 1:
                        mid_num = [index, index]
                else:
                    if mid_num[0] == -1 and current_count + c >= mid_count:
                        mid_num[0] = index
                    if mid_num[1] == -1 and current_count + c >= mid_count + 1:
                        mid_num[1] = index
                average_sum += index * c

                if count[most] < c:
                    most = index
                current_count += c

        return [temp_min, temp_max, average_sum / total_count, sum(mid_num) / 2, most]