LeetCode1093-大样本统计

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/statistics-from-a-large-sample/

中文链接：https://leetcode-cn.com/problems/statistics-from-a-large-sample/

题目详述

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

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

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

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

示例 1：

1
2
输入：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：

1
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 以内就会被视为正确答案

题目详解

  • 最小值、最大值、平均值、众数都比较容易求得。

  • 中位数要麻烦一点，它可能是中间的一个数或者是中间两个数的平均值。要特别注意中间两个数不同的情况。

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
42
public class LeetCode_01093 {

    public double[] sampleStats(int[] count) {
        int n = count.length;
        int mode = 0, modeMax = 0;
        int min = -1, max = -1;
        double avg = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (count[i] > modeMax) {
                modeMax = count[i];
                mode = i;
            }
            if (count[i] != 0) {
                cnt += count[i];
                avg += count[i] * i;
                if (min == -1) min = i;
                max = i;
            }
        }
        avg /= cnt;
        // 求中位数
        double mid = 0;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += count[i];
            if (sum << 1 > cnt) {
                mid = i;
                break;
            } else if (sum << 1 == cnt) {
                for (int j = i + 1; j < n; ++j) {
                    if (count[j] != 0) {
                        mid = (i + j) / 2.0;
                        break;
                    }
                }
                break;
            }
        }
        return new double[]{min, max, avg, mid, mode};
    }
}