TNotes.leetcode

Appearance

⏰1093. 大样本统计【中等】

1093. 大样本统计【中等】 ​

1. 📝 题目描述 ​

我们对 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^9
  • 1 <= sum(count) <= 10^9
  • count 的众数是 唯一 的

2. 🎯 s.1 - 模拟 ​

js
/**
 * @param {number[]} count
 * @return {number[]}
 */
var sampleStats = function (count) {
  let min = -1,
    max = -1,
    mode = 0,
    total = 0,
    sum = 0,
    maxFreq = 0
  for (let i = 0; i < 256; i++) {
    if (count[i] === 0) continue
    if (min === -1) min = i
    max = i
    total += count[i]
    sum += i * count[i]
    if (count[i] > maxFreq) {
      maxFreq = count[i]
      mode = i
    }
  }
  const mean = sum / total
  // find median
  let m1 = -1,
    m2 = -1
  const half1 = Math.floor((total - 1) / 2),
    half2 = Math.floor(total / 2)
  let acc = 0
  for (let i = 0; i < 256; i++) {
    acc += count[i]
    if (m1 === -1 && acc > half1) m1 = i
    if (m2 === -1 && acc > half2) m2 = i
  }
  return [min, max, mean, (m1 + m2) / 2, mode]
}
  • 时间复杂度：O(1)，遥历固定 256 个元素
  • 空间复杂度：O(1)，只使用常数级别的额外空间

算法思路：

  • 第一次遍历 count 数组，统计最小值、最大值、总数、总和和众数
  • 第二次遍历累加计数，找到中位数对应的两个位置（奇数个时两个位置相同）
  • 均值 = 总和 / 总数，中位数 = 两个中间位置值的平均