字典中移除间隔n天内的日期，仅保留最后列出的日期

核心逻辑 #

将每个键对应的日期列表中，所有可通过≤n天间隔连通的日期归为一类（比如A和B间隔≤n、B和C间隔≤n，则A/B/C同组），仅保留该类在原列表中最后出现的日期；间隔超过n天的日期单独保留，最终输出顺序与原列表中保留元素的出现顺序一致。

代码实现 #

from datetime import date

def process_dates(date_list, n_days):
    # 转换日期并保留原列表索引
    date_with_metadata = []
    for idx, d_str in enumerate(date_list):
        year, month, day = map(int, d_str.split('-'))
        d = date(year, month, day)
        date_with_metadata.append((d, idx, d_str))
    
    # 并查集初始化
    parent = list(range(len(date_with_metadata)))
    
    def find(u):
        # 路径压缩优化
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    def union(u, v):
        # 合并两个集合
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root
    
    # 按日期排序后，相邻合并连通的日期组
    sorted_dates = sorted(date_with_metadata, key=lambda x: x[0])
    for i in range(1, len(sorted_dates)):
        prev_date = sorted_dates[i-1][0]
        curr_date = sorted_dates[i][0]
        if (curr_date - prev_date).days <= n_days:
            # 合并原列表中对应的索引位置
            union(sorted_dates[i-1][1], sorted_dates[i][1])
    
    # 按聚类分组，保留每组中最后出现的日期（原索引最大）
    clusters = {}
    for idx in range(len(date_with_metadata)):
        root = find(idx)
        clusters.setdefault(root, []).append(date_with_metadata[idx])
    
    kept_dates = []
    for cluster in clusters.values():
        # 筛选原索引最大的元素
        last_appeared = max(cluster, key=lambda x: x[1])
        kept_dates.append((last_appeared[1], last_appeared[2]))
    
    # 按原列表顺序排序保留的日期
    kept_dates.sort(key=lambda x: x[0])
    return [d_str for _, d_str in kept_dates]

def process_date_dict(input_dict, n_days=30):
    output_dict = {}
    for key, dates in input_dict.items():
        output_dict[key] = process_dates(dates, n_days)
    return output_dict

测试示例 #

# 输入字典
input_dict = {
    'a': ['2020-12-11'],
    'b': ['2020-05-30', '2022-09-11'],
    'c': ['2021-07-28', '2022-07-20', '2022-07-07', '2022-06-30'],
    'd': ['2022-04-17', '2022-04-18', '2022-04-15', '2022-08-20']
}

# 处理（默认30天间隔）
result = process_date_dict(input_dict)
print(result)

输出结果：

{
    'a': ['2020-12-11'],
    'b': ['2020-05-30', '2022-09-11'],
    'c': ['2021-07-28', '2022-06-30'],
    'd': ['2022-04-15', '2022-08-20']
}

自定义天数用法 #

只需在调用时传入n_days参数即可，比如设置60天间隔：

result_60d = process_date_dict(input_dict, n_days=60)

效率说明 #

• 并查集的操作时间复杂度近似为O(α(N))（α为阿克曼函数的反函数，几乎是常数）
• 日期排序的时间复杂度为O(N log N)
• 整体处理大列表时性能高效，适合批量处理日期数据

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