或许不安或许迷惑,但迷雾遮挡不住前方的光亮,有梦可待。
LC每日一题,参考1093. 大样本统计 - 力扣(Leetcode)。
题目
我们对 0
到 255
之间的整数进行采样,并将结果存储在数组 count
中:count[k]
就是整数 k
在样本中出现的次数。
计算以下统计数据:
-
minimum
:样本中的最小元素。 -
maximum
:样品中的最大元素。 -
mean
:样本的平均值,计算为所有元素的总和除以元素总数。 -
median
:- 如果样本的元素个数是奇数,那么一旦样本排序后,中位数
median
就是中间的元素。 - 如果样本中有偶数个元素,那么中位数
median
就是样本排序后中间两个元素的平均值。
- 如果样本的元素个数是奇数,那么一旦样本排序后,中位数
-
mode
:样本中出现次数最多的数字。保众数是 唯一 的。
以浮点数数组的形式返回样本的统计信息 **[minimum, maximum, mean, median, mode]
。与真实答案误差在 **10^5
**内的答案都可以通过。
输入: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,因为它在样本中出现的次数最多。
输入: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,因为它在样本中出现的次数最多。
解题思路
- 模拟:直接遍历模拟,第一次遍历样本长度,第二次遍历统计数据。
模拟两次便利
class Solution {
public double[] sampleStats(int[] count) {
//统计最值
double minimum = -1,maximum = 0,sum = 0;
int mode = 0,size = 0;
double num1 = -1,num2 = -1;
for(int i = 0; i < count.length; size += count[i++]);//求长度
boolean flag = size%2==0;
for(int i = 0,cnt = -1; i < count.length; i++) {
double len = count[i];
if(len == 0) continue;
if(minimum == -1) minimum = i;//最小值
maximum = i;//最大值
sum += (double)i * len; //平均值
if(flag&&num1==-1 &&size/2-1 > cnt&& size/2-1 <= cnt+len) num1 = i;
if(num2==-1 &&size/2 > cnt && size/2 <= cnt+len) num2 = i;
cnt += len;//中位数
if(len > count[mode]) mode = i;
}
return new double[]{minimum,maximum,sum/size,flag?(num1+num2)/2 : num2,mode};
}
}
复杂度分析
- 时间复杂度:
O(n)
,一重循环遍历,n
为数组长度固定为256
。 - 空间复杂度:
O(1)
,只使用常量空间。
网友评论