LeetCode-1093 大样本统计

比眉伴天荒 2022-01-05 07:43 215阅读 0赞

**题目链接：**

源自LeetCode第142场周赛

[https://leetcode-cn.com/contest/weekly-contest-142/problems/statistics-from-a-large-sample/][https_leetcode-cn.com_contest_weekly-contest-142_problems_statistics-from-a-large-sample]

**题目描述：**

我们对 `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]

**提示：**

1.  `count.length == 256`
2.  `1 <= sum(count) <= 10^9`
3.  计数表示的众数是唯一的
4.  答案与真实值误差在 `10^-5` 以内就会被视为正确答案

**题目大意：**

给出一个数组count\[256\]，count\[i\]表示数字i（i大于等于0小于等于255）在一个序列中出现的次数，要求统计出序列的最小值、最大值、平均数、中位数和众数。

**思路：**

**最小值就是第一个count\[i\]大于0的i；最大值就是最后一个count\[i\]>0的i；平均数是对于所有count\[i\]>0，i\*count\[i\]的加和除以序列中数字的个数cnt；找到最大的count\[i\]，i就是众数。**

中位数要分情况讨论。定义一个新变量nextcount=0，类似于cnt的统计，重新遍历count数组，对于每个count\[i\]>0，nextcnt为出现i之前所有出现的数的个数。

**若统计出来的序列中数字的个数cnt为奇数，**则nextcnt<=cnt/2并且nextcnt+count\[i\]>cnt/2时，此时i就是中位数。例如cnt=5，序列为\{1,2,2,3,5\}，cnt/2=5/2=2，i为2时，nextcnt=1，count\[i\]=2，nextcnt=1<2并且nextcnt+count\[2\]=3>2，2就是中位数。

**若统计出来的序列中数字的个数cnt为偶数，**则要对nextcnt分情况讨论，如果nextcnt已经加到了cnt/2（即nextcnt==cnt/2），则上一个出现的数pre一定是偶数个数字的序列中运算得到中位数所需的第一部分，当前遍历到的count\[i\]>0的i就是运算得到中位数所需的第二部分，(第一部分+第二部分)/2即得到中位数，例如cnt=6，序列为\{1,2,2,4,4,5\}，i为4时，pre=2，nextcnt=3=cnt/2，nextcnt+count\[4\]=3+2=5>cnt/2，中位数=(pre+i)/2=(2+4)/2=3；还有一种是nextcnt<cnt/2并且nextcnt+count\[i\]>cnt/2，此时i就是中位数，例如cnt=6，序列为\{1,3,3,3,3,5\}，i为3时，nextcnt=1<cnt/2，nextcnt+count\[3\]=1+4=5>cnt/2，3就是中位数。

**上AC代码：**

class Solution {
    public:
        vector<double> sampleStats(vector<int>& count) {
            vector<double> ret;
            int i,j;
            //众数
            double most=-1;
            //中位数
            double medium=-1;
            //最小值
            double xiao=0x3f3f3f3f;
            //最大值
            double da=-0x3f3f3f3f;
            //平均值
            double pingjun=-1;
            //出现次数最多的数出现了多少次
            int maxsum=-0x3f3f3f3f;
            //用于统计序列中数的个数
            int cnt=0;
            //序列和 用于求平均值
            double sum=0;
            
            for(i=0;i<256;i++)
            {
                if(count[i]>0)
                {
                    //找最大
                    if(i>da)
                    {
                        da=i;
                    }
                    //找最小
                    if(i<xiao)
                    {
                        xiao=i;
                    }
                    //为了求平均
                    sum+=i*count[i];
                    
                    cnt+=count[i];
                    //找众数
                    if(count[i]>maxsum)
                    {
                        most=i;
                        maxsum=count[i];
                    }
                }
            }
            
            ret.push_back(xiao);
            ret.push_back(da);
            //求平均值
            pingjun=sum/cnt;
            ret.push_back(pingjun);
            //找中位数
            int nextcnt=0;
            if(cnt%2==1)
            {
                //奇数
                for(i=0;i<256;i++)
                {
                    if(count[i]>0)
                    {
                        if(nextcnt<=cnt/2&&nextcnt+count[i]>cnt/2)
                        {
                            medium=i;
                            break;
                        }
                        nextcnt+=count[i];
                    }
                }
            }
            else
            {
                //偶数
                int pre=-1;
                for(i=0;i<256;i++)
                {
                    if(count[i]>0)
                    {
                        if(nextcnt<cnt/2&&nextcnt+count[i]>cnt/2)
                        {
                            medium=i;
                            break;
                        }
                        else if(nextcnt==cnt/2&&nextcnt+count[i]>cnt/2)
                        {
                            medium=(i+pre)/2.0;
                            break;
                        }
                        nextcnt+=count[i];
                        pre=i;
                    }
                }
            }
            ret.push_back(medium);
            ret.push_back(most);
            
            return ret;
        }
    };

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[https_leetcode-cn.com_contest_weekly-contest-142_problems_statistics-from-a-large-sample]: https://leetcode-cn.com/contest/weekly-contest-142/problems/statistics-from-a-large-sample/
[20200227123106884.jpg]: /images/20211229/c983183c6ab146c88569021546934201.png