大样本统计【LC1093】
我们对
0
到255
之间的整数进行采样,并将结果存储在数组count
中:count[k]
就是整数k
在样本中出现的次数。计算以下统计数据:
minimum
:样本中的最小元素。maximum
:样品中的最大元素。mean
:样本的平均值,计算为所有元素的总和除以元素总数。median
:
- 如果样本的元素个数是奇数,那么一旦样本排序后,中位数
median
就是中间的元素。- 如果样本中有偶数个元素,那么中位数
median
就是样本排序后中间两个元素的平均值。mode
:样本中出现次数最多的数字。保众数是 唯一 的。以浮点数数组的形式返回样本的统计信息
[minimum, maximum, mean, median, mode]
。与真实答案误差在10-5
内的答案都可以通过。
简单模拟
-
思路
按照定义进行模拟,难点在于平均值的越界处理和中位数的求法
-
平均值:为了避免越界,使用long类型存储所有值之和
-
中位数(下标从1开始)
- 如果总个数为奇数,那么中位数为第 ⌈ n u m 2 ⌉ \lceil \frac{num}{2} \rceil ⌈2num⌉个数
- 如果总个数为偶数数,那么中位数为第$ \frac{num}{2} 个和第 个和第 个和第 \frac{num}{2} + 1$个数的平均值
因此可以使用辅助函数寻找数组中的第 i i i个数
-
-
实现
class Solution {int[] count;public double[] sampleStats(int[] count) {this.count = count;double[] res = new double[5];int n = count.length;int num = 0, maxCount = 0;long sum = 0;res[0] = 256;for (int i = 0; i < n; i++){num += count[i];sum += (long)i * count[i];if (count[i] != 0){ res[0] = Math.min(res[0], i);// 最小值res[1] = Math.max(res[1], i);// 最大值}if (count[maxCount] < count[i]){maxCount = i;// 众数}}res[2] = 1.0 * sum / num;// 平均值res[3] = num % 2 == 1 ? find(num / 2 + 1) : (find(num / 2) + find(num / 2 + 1)) / 2.0;// 中位数res[4] = maxCount;// 众数 return res;}public int find(int index){int i = -1, cnt = 0;while (cnt < index){cnt += count[++i];}return i;} }
- 复杂度
- 时间复杂度: O ( n ) \mathcal{O}(n) O(n)
- 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)
- 复杂度