乐趣区

1093大样本统计

前言

Weekly Contest 142 的 大样本统计:

我们对 0255 之间的整数进行采样,并将结果存储在数组 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 其实算是一个压缩数据后的数组。

我们对 0255 之间的整数进行采样,并将结果存储在数组 count 中:count[k] 就是整数 k 的采样个数。

简单来说就是,数组 count 的第 k 个元素就是 k 在压缩前的数组中出现 count[k] 个。以 示例 1 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]

解压的过程如下:

第 0 个元素为 0,则解压后的数组为[]
第 1 个元素为 4,则解压后的数组为[1,1,1,1]
第 2 个元素为 3,则解压后的数组为[1,1,1,1,2,2,2]
第 3 个元素为 2,则解压后的数组为[1,1,1,1,2,2,2,3,3]
第 4 个元素为 2,则解压后的数组为[1,1,1,1,2,2,2,3,3,4,4]
......
省略后续步骤

搞清楚 count 的数据特征后,选择使用 TreeMapcount进行处理,将有效数字及其出现个数存储起来(有效数字指的是 count[k] 不为 0 的元素)。根据就是根据题目要求分别处理以下指标:

  • 最小值:TreeMap中第一个key
  • 最大值:TreeMap中最后一个key
  • 平均值:TreeMapkey 之和除以 value 之和
  • 中位数:

    1. 计算出数组实际的元素个数(即 value 之和)
    2. 根据元素个数的奇偶性,获取对应的值
  • 众数:出现次数最多的数字,即 TreeMapvalue最大的键值对的key

实现代码

    /**
     * 1093. 大样本统计
     *
     * @param count
     * @return
     */
    public double[] sampleStats(int[] count) {
        // 使用 TreeMap 有序存储数字及其出现次数
        TreeMap<Integer, Integer> countMap = new TreeMap<>();
        double[] result = new double[5];
        // 总和
        double sum = 0L;
        // 数字出现总次数
        double total = 0L;
        // 最大出现次数
        long maxTimes = 0;
        // 最小值
        double min;
        // 最大值
        double max;
        // 平均值
        double average;
        // 中位数
        double middle = 0;
        // 众数,出现次数最多的数字
        double mode = 0;
        for (int i = 0; i < count.length; i++) {if (count[i] != 0) {countMap.put(i, count[i]);
                sum = sum + i * count[i];
                total += count[i];
                if (count[i] > maxTimes) {maxTimes = count[i];
                    mode = i;
                }
            }
        }
        min = countMap.firstKey().doubleValue();
        max = countMap.lastKey().doubleValue();
        average = sum / total;
        // 是否为奇数
        boolean odd = total % 2 != 0;
        // 中位数索引
        int middleIndex = (int) ((total - 1) / 2);
        int index = -1;
        Iterator<Map.Entry<Integer, Integer>> it = countMap.entrySet().iterator();
        while (it.hasNext()) {Map.Entry<Integer, Integer> entry = it.next();
            int num = entry.getKey();
            int times = entry.getValue();
            index += times;
            if (index > middleIndex) {
                middle = num;
                break;
            } else if (index == middleIndex) {if (odd) {
                    middle = num;
                    break;
                } else {middle = (num + it.next().getKey()) / 2.0;
                    break;
                }
            }
        }
        result[0] = min;
        result[1] = max;
        result[2] = average;
        result[3] = middle;
        result[4] = mode;
        return result;
    }
退出移动版