Java编写findEpidemics函数判断流行病连续k日发病超n次逻辑问题

核心逻辑说明 #

你现有按DiagnosisMetric（疾病+日期）分组统计日发病数的逻辑是正确的，接下来需要做3步处理：

1. 将统计结果按疾病维度聚合，得到每个疾病对应的「日期-发病数」映射
2. 对每个疾病的所有病例日期按升序排序
3. 用滑动窗口遍历所有连续k天的区间，只要任意区间的总发病数超过n，就判定为流行病

完整实现代码 #

import java.util.*;
import java.util.stream.Collectors;

public Collection<String> findEpidemics(List<Diagnosis> diagnoses, int k, int n) {
    // 前置参数校验
    if (k <= 0 || n < 0 || diagnoses == null || diagnoses.isEmpty()) {
        return Collections.emptySet();
    }

    // 首先统计发病次数：按疾病+日期分组，得到每日发病数
    Map<DiagnosisMetric, Long> collect = diagnoses.stream()
            .collect(Collectors.groupingBy(DiagnosisMetric::new, Collectors.counting()));

    // 步骤1：按疾病名称聚合，得到每个疾病对应的<日期, 日发病数>映射
    // 注：此处假设Disease类提供getName()方法返回疾病名称，DiagnosisMetric类提供getDisease()、getDay()方法返回对应属性
    Map<String, Map<Integer, Long>> diseaseDayCount = collect.entrySet().stream()
            .collect(Collectors.groupingBy(
                    entry -> entry.getKey().getDisease().getName(),
                    Collectors.toMap(entry -> entry.getKey().getDay(), Map.Entry::getValue)
            ));

    Set<String> epidemics = new HashSet<>();

    // 步骤2：遍历每个疾病校验流行病规则
    for (Map.Entry<String, Map<Integer, Long>> entry : diseaseDayCount.entrySet()) {
        String diseaseName = entry.getKey();
        Map<Integer, Long> dayCountMap = entry.getValue();
        // 对该疾病的所有有病例的日期升序排序
        List<Integer> sortedDays = dayCountMap.keySet().stream()
                .sorted()
                .toList();
        int dayCount = sortedDays.size();
        if (dayCount == 0) continue;

        // 步骤3：滑动窗口校验连续k天的总发病数
        boolean isEpidemic = false;
        for (int i = 0; i < dayCount; i++) {
            int windowStart = sortedDays.get(i);
            int windowEnd = windowStart + k - 1; // 连续k天的结束日期
            long total = 0;
            // 累加当前窗口内的所有发病数
            for (int j = i; j < dayCount; j++) {
                int currentDay = sortedDays.get(j);
                if (currentDay > windowEnd) break; // 超出窗口范围直接终止
                total += dayCountMap.get(currentDay);
                if (total > n) {
                    isEpidemic = true;
                    break;
                }
            }
            if (isEpidemic) {
                epidemics.add(diseaseName);
                break;
            }
        }
    }
    return epidemics;
}

逻辑验证示例 #

拿你给出的诊断列表示例，假设参数k=2，n=2：

• 霍乱的有病例日期为[0,1,6]，第一个窗口区间为[0,1]，总发病数2+1=3>2，直接判定为流行病
• 登革热的有病例日期为[2]，窗口区间为[2,3]，总发病数2，不大于n=2，不判定为流行病

性能优化建议 #

如果病例的日期跨度很大，可以用前缀和+二分查找替代内层循环，将时间复杂度从O(m²)降低到O(m log m)，其中m为单个疾病的有病例日期数量。

内容的提问来源于stack exchange，提问作者StephenHawkingi