leetcode
leetcode 1001 ~ 1050
大样本统计

大样本统计

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用IntStream来遍历count数组。
 * 2. 通过filter和summaryStatistics找到最小值、最大值和求和。
 * 3. 计算总和sum和总数totalCount,得出均值。
 * 4. 使用IntStream和Collectors来计算中位数和众数。
 */
import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.*;

public class Solution {
    public double[] sampleStats(int[] count) {
        int min = IntStream.range(0, count.length).filter(i -> count[i] > 0).findFirst().orElse(-1);
        int max = IntStream.range(0, count.length).filter(i -> count[i] > 0).reduce((a, b) -> b).orElse(-1);
        long totalCount = IntStream.of(count).sum();
        double mean = IntStream.range(0, count.length).mapToDouble(i -> i * count[i]).sum() / totalCount;
        int mode = IntStream.range(0, count.length).boxed().max(Comparator.comparingInt(i -> count[i])).orElse(-1);
        long mid = (totalCount + 1) / 2;
        long currCount = 0;
        double median = 0;
        List<Integer> list = IntStream.range(0, count.length).boxed().collect(Collectors.toList());
        for (int i : list) {
            currCount += count[i];
            if (currCount >= mid) {
                if (totalCount % 2 == 1) {
                    median = i;
                } else {
                    if (currCount == mid) {
                        for (int j = i + 1; j < count.length; j++) {
                            if (count[j] > 0) {
                                median = (i + j) / 2.0;
                                break;
                            }
                        }
                    } else {
                        median = i;
                    }
                }
                break;
            }
        }
        return new double[]{min, max, mean, median, mode};
    }
}

解释

方法:

题解通过一次遍历数组 count,计算最小值、最大值、平均值、中位数和众数。最小值和最大值通过检查每个数字的计数是否大于零并更新最小或最大索引来得到。平均值通过累加所有数字乘以其出现次数再除以总数计算。中位数通过累积出现的次数直到达到或超过总数的一半来确定。如果总元素数是奇数,中位数是累计到的那个数;如果是偶数,则取累积到的两个数的平均值。众数是出现次数最多的数字。

时间复杂度:

O(256) => O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
如何从count数组中准确地确定最小值和最大值,尤其是在存在大量0计数的情况下?
在count数组中,每个索引代表一个数字,而该索引的值代表该数字出现的次数。为了确定最小值,从count数组的开始遍历,找到第一个计数大于0的索引,这个索引即为最小值。同样,为了找到最大值,从count数组的末尾向前遍历,直到找到第一个计数大于0的索引,这个索引即为最大值。这种方法确保了即便数组中有大量的0计数(即某些数值未出现),也能准确找到出现过的最小和最大数值。
🦆
在计算平均值mean时,是否需要考虑整数溢出的问题,特别是当样本大小非常大的情况下?
是的,当处理非常大的数据集时,计算平均值前累加总和可能导致整数溢出。为了避免这个问题,可以采用更大范围的数据类型(如Python中的长整型),或者逐步计算平均值来减小每一步的数值范围,比如使用在线算法进行平均值的更新。在Python中,整数通常会自动转换为长整型以避免溢出,但在其他语言中,如C++或Java,需要显式使用长整型数据类型来处理大数的累加。
🦆
计算中位数时,如何处理累积频率恰好等于n/2的情况,特别是在元素个数为偶数时?
计算中位数时,如果元素总数n为偶数,中位数是第n/2个元素和第n/2+1个元素的平均值。当累积频率恰好等于n/2时,表示第n/2个元素已经包括在内,因此这个元素应当是中位数的一部分。然后继续遍历直到找到下一个非零频率的元素,这个元素则是第n/2+1个元素。取这两个元素的值的平均,即为最终的中位数。如果累积频率直接跳过了n/2而没有等于的情况,则中位数可能刚好是一个具体的值,而不需要平均。
🦆
为何在找众数时只记录了一个最大频率的数字,而没有考虑可能存在两个或更多具有相同最高频率的数字?
在这个题解中,众数的定义是出现频率最高的单一数字。如果有多个数字具有相同的最高频率,题解中的实现只记录了首次遇到的那个数字。这种选择是基于简化实现的考虑。然而,如果需要考虑所有具有最高频率的数字,应该修改算法来收集所有这些数字,而不只是第一个遇到的。这通常涉及使用一个列表或其他数据结构来存储所有频率最高的数字,并在最后返回所有这些数字。

相关问题