题目描述

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 的采样个数。

我们以 浮点数 数组的形式，分别返回样本的最小值、最大值、平均值、中位数和众数。其中，众数是保证唯一的。

我们先来回顾一下中位数的知识：

• 如果样本中的元素有序，并且元素数量为奇数时，中位数为最中间的那个元素；
• 如果样本中的元素有序，并且元素数量为偶数时，中位数为中间的两个元素的平均值。

样例

输入：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 = [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 以内就会被视为正确答案。

算法

(模拟) $O(n)$

1. 最小值、最大值、平均值和众数按照定义模拟即可。
2. 对于中位数，分成奇数和偶数个数进行讨论，注意判断边界情况。

时间复杂度

• 扫描数组常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需定义额外的变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    vector<double> sampleStats(vector<int>& count) {
        vector<double> ans;
        for (int i = 0; i < 256; i++)
            if (count[i] > 0) {
                ans.push_back(i);
                break;
            }

        for (int i = 255; i >= 0; i--)
            if (count[i] > 0) {
                ans.push_back(i);
                break;
            }

        int tot = 0;
        double sum = 0;
        for (int i = 0; i < 256; i++) {
            sum += count[i] * i;
            tot += count[i];
        }
        ans.push_back(sum / tot);

        int tot2 = 0;
        if (tot % 2 == 0) {
            for (int i = 0 ; i < 256; i++) {
                if (tot2 < tot / 2 && tot2 + count[i] > tot / 2) {
                    ans.push_back(i);
                    break;
                } else if (tot2 == tot / 2) {
                    for (int j = i - 1; j >= 0; j--)
                        if (count[j] > 0) {
                            ans.push_back((i + j) / 2.0);
                            break;
                        }
                    break;
                }
                tot2 += count[i];
            }
        } else {
            for (int i = 0 ; i < 256; i++) {
                if (tot2 <= tot / 2 && tot2 + count[i] > tot / 2) {
                    ans.push_back(i);
                    break;
                }
                tot2 += count[i];
            }
        }

        int maxi = 0;
        for (int i = 1; i < 256; i++)
            if (count[maxi] < count[i])
                maxi = i;
        ans.push_back(maxi);

        return ans;
    }
};