【1093. 大样本统计】

来源：力扣（LeetCode）

描述：

我们对 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，因为它在样本中出现的次数最多。
1
2
3
4
5
6
7

示例 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，因为它在样本中出现的次数最多。
1
2
3
4
5
6
7

提示：

• count.length == 256
• 0 <= count[i] <= 10⁹
• 1 <= sum(count) <= 10⁹
• count 的众数是 唯一 的

方法：直接模拟

思路与算法

根据题意可知，需要计算样本数组的以下值：

• minimum：样本中的最小元素。
• maximum：样品中的最大元素。
• mean：样本的平均值，计算为所有元素的总和除以元素总数。
• median：样本的中位数。
  • 如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
  • 如果样本中有偶数个元素，那么中位数 median 就是样本排序后中间两个元素的平均值。
• mode：样本中出现次数最多的数字。保众数是「唯一」的。

根据以上定义我们分别进行模拟计算即可，对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。

• minimum：定义为样本中的最小元素，由于从 0 到 255 采样，而题目中给定的每个整数出现的次数，我们从 0 开始遍历找到第一个 count[i] > 0 的整数 i 即为样本最小元素。

• maximum：定义为样本中的最大元素，我们从 255 开始倒序遍历找到第一个 count[i] > 0 的整数 i 即为样本最大元素。

• mean：样本的平均值，我们计算样本数据的和，并除以样本的采样次数即可，其中样本数据的和为 ${\sum }_{i=0}^{255}count[i]\ast i$，采样次数为 ${\sum }_{i=0}^{255}count[i]$，样本的平均值 mean = $\frac{{\sum }_{i=0}^{255}count[i]\ast i}{{\sum }_{i=0}^{255}count[i]}$。

• median：找到样本的中位数，样本的中位数稍微麻烦一些，已经知道采样总的次数为 total = ${\sum }_{i=0}^{255}$count[i]，此时:

  • 如果 total 为偶数：我们从小到大找到排序为 $\frac{total}{2}$ 与 $\frac{total}{2}$ + 1的元素，此时中位数即为二者和的平均值；
  • 如果 total 为奇数：我们从小到大找到排序为 $\frac{total+1}{2}$ 的元素，此时中位数即为该元素。
  • 每次查找时统计当前已经遍历过的样本数目，cnt 表示从当前从元素 0 开始到 i 的样本总数，定义中位数的两个元素排序取值范围为 [left, right]，如果当前元素刚好处于中位数的取值范围则将其加入计算即可。

• mode：样本中出现次数最多的数字，找到 count[i] 的最大值，此时 i 即为样本出现次数最多的数字。

代码：

class Solution {
public:    
    vector<double> sampleStats(vector<int>& count) {
        int n = count.size();
        int total = accumulate(count.begin(), count.end(), 0);
        double mean = 0.0;
        double median = 0.0;
        int minnum = 256;
        int maxnum = 0;
        int mode = 0;

        int left = (total + 1) / 2;
        int right = (total + 2) / 2;
        int cnt = 0;
        int maxfreq = 0;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (long long)count[i] * i;
            if (count[i] > maxfreq) {
                maxfreq = count[i];
                mode = i;
            }
            if (count[i] > 0) {
                if (minnum == 256) {
                    minnum = i;
                }
                maxnum = i;
            }
            if (cnt < right && cnt + count[i] >= right) {
                median += i;
            }
            if (cnt < left && cnt + count[i] >= left) {
                median += i;
            }
            cnt += count[i];
        }
        mean = (double) sum / total;
        median = median / 2.0;
        return {(double)minnum, (double)maxnum, mean, median, (double)mode};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了90.72%的用户
复杂度分析
时间复杂度：O(n)，其中 n 表示给定的数组的长度。根据题意可知道只需遍历数组两次，总体时间复杂度为 O(n)。
空间复杂度：O(1)。除返回值以外，不需要额外的空间。
author：LeetCode-Solution