LeetCode解法汇总1093. 大样本统计

目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：力扣

描述：

我们对 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] <= 109
1 <= sum(count) <= 109
count 的众数是唯一的

解题思路：

/**

* 最小，最大，平均值，最多都比较简单，重点是中位数。

* 因为数量很多，我们挨个去统计肯定不合适，

* 所以我们首先可以总数量，然后分别求matchleft和matchright代表左右的中位数，如果是基数的话matchright=matchright。

* 然后我们不断的sum去减掉count[i]的值，当num <= matchright时，说明已经走到了右侧的中位数，这时候记录其值到medianValue。num <= matchleft时也是一样。

* 最后medianValue/2就是我们的预期中位数。

代码：

#include <iostream>
#include <map>
#include <list>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

/**
 * 最小，最大，平均值，最多都比较简单，重点是中位数。
 * 因为数量很多，我们挨个去统计肯定不合适，
 * 所以我们首先可以总数量，然后分别求matchleft和matchright代表左右的中位数，如果是基数的话matchright=matchright。
 * 然后我们不断的sum去减掉count[i]的值，当num <= matchright时，说明已经走到了右侧的中位数，这时候记录其值到medianValue。num <= matchleft时也是一样。
 * 最后medianValue/2就是我们的预期中位数。
 */
class Solution
{
public:
    vector<double> sampleStats(vector<int> &count)
    {
        vector<double> list;
        double minValue = -1;
        double maxValue = -1;
        double meanValue = 0;
        double medianValue = 0;
        double modeValue = 0;
        // 最大数量
        int maxNum = 0;
        // 总数量
        int num = 0;
        // 总的累加值
        double sum = 0;
        for (int i = 0; i < count.size(); i++)
        {
            if (count[i] == 0)
            {
                continue;
            }
            num += count[i];
            sum += (count[i] * (long)i);
            maxValue = i;
            if (minValue == -1)
            {
                minValue = i;
            }
            if (count[i] > maxNum)
            {
                modeValue = i;
                maxNum = count[i];
            }
        }
        meanValue = sum / num;

        // 求中位数
        int matchleft = 0;
        int matchright = 0;
        if (num % 2 == 0)
        {
            matchleft = num / 2 - 1;
            matchright = num / 2;
        }
        else
        {
            matchleft = num / 2;
            matchright = num / 2;
        }

        for (int i = 0; i < count.size(); i++)
        {
            num -= count[i];
            if (num <= matchright)
            {
                medianValue += i;
                matchright = -1;
            }
            if (num <= matchleft)
            {
                medianValue += i;
                break;
            }
        }
        medianValue = medianValue / 2;
        list.push_back(minValue);
        list.push_back(maxValue);
        list.push_back(meanValue);
        list.push_back(medianValue);
        list.push_back(modeValue);
        return list;
    }
};