LeetCode 1093. 大样本统计
LeetCode 1093. 大样本统计
Michael阿明
修改于 2020-07-13 11:48:57
修改于 2020-07-13 11:48:57
1. 题目
我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 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 以内就会被视为正确答案来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/statistics-from-a-large-sample
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution {
public:
vector<double> sampleStats(vector<int>& count) {
int i, MIN = -1, MAX, avg, median = 0, mode;
int n = 0, ni = 0, N;
long sum = 0;
for(i = 0; i < count.size(); ++i)
{
if(count[i])
{
if(MIN == -1)
MIN = i;//第一个最小的数 i
MAX = i;//最大的数 i
n += count[i];//个数累加
sum += count[i]*i;//求和
if(count[i] > ni)//单个数 最大的个数
{
ni = count[i];
mode = i;//众数
}
}
}
vector<double> ans({MIN,MAX,double(sum)/n,0,mode});
ni = 0;
bool flag = false;
for(i = 0; i < count.size(); ++i)
{ //寻找中位数
if(n%2)//总的个数是奇数个
{
if(ni+count[i] < n/2+1)
ni += count[i];
else
{
ans[3] = i;
break;
}
}
else//偶数个
{
N = ni + count[i];
if(N < n/2)
ni += count[i];
else if(N >= n/2 && N < n/2+1)
{
ans[3] = i;
flag = true;//中位数，卡在两个数上
}
else
{
if(!flag)
{
ans[3] = i;
break;
}
else
{
ans[3] = double(ans[3]+i)/2;
break;
}
}
}
}
return ans;
}
};8 ms 8.6 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-04-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录