leetcode
leetcode 551 ~ 600
设计日志存储系统

设计日志存储系统

难度:

标签:

题目描述

代码结果

运行时间: 44 ms, 内存: 16.7 MB


/*
 * Leetcode 635: Design Log Storage System
 * 
 * Solution using Java Streams:
 * 1. Use a list to store log entries as a pair of (id, timestamp).
 * 2. Use a map to define the granularity levels (year, month, day, hour, minute, second).
 * 3. For the retrieve function, use Java Streams to filter logs based on the given start and end timestamps according to the specified granularity.
 */
 
import java.util.*;
import java.util.stream.Collectors;
 
public class LogSystem {
    private List<int[]> logs;
    private Map<String, Integer> granularityMap;
    
    public LogSystem() {
        logs = new ArrayList<>();
        granularityMap = new HashMap<>();
        granularityMap.put("Year", 4);
        granularityMap.put("Month", 7);
        granularityMap.put("Day", 10);
        granularityMap.put("Hour", 13);
        granularityMap.put("Minute", 16);
        granularityMap.put("Second", 19);
    }
    
    public void put(int id, String timestamp) {
        logs.add(new int[]{id, timestamp.hashCode()});
    }
    
    public List<Integer> retrieve(String s, String e, String gra) {
        int len = granularityMap.get(gra);
        int startHash = s.substring(0, len).hashCode();
        int endHash = e.substring(0, len).hashCode();
        return logs.stream()
                    .filter(log -> log[1] >= startHash && log[1] <= endHash)
                    .map(log -> log[0])
                    .collect(Collectors.toList());
    }
}
 

解释

方法:

这个题解使用了哈希表来存储日志的时间戳和对应的 ID。在插入日志时,直接将时间戳作为键,ID 作为值存入哈希表。在检索日志时,根据给定的时间范围和粒度,遍历哈希表中的所有键值对,将时间戳截取到对应粒度,如果在给定的时间范围内,就将对应的 ID 加入结果列表。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在处理较大数据量时,遍历哈希表的所有键值对是否有可能导致性能问题?是否有更高效的数据结构或方法来优化检索过程?
是的,在处理大量数据时,遍历哈希表的所有键值对确实可能导致性能问题,因为这种操作的时间复杂度是O(n),其中n是哈希表中的元素数量。这在大数据场景下会变得低效。为了优化检索过程,可以考虑使用平衡二叉搜索树(例如红黑树)或时间轴映射的数据结构(如TreeMap在Java中)来存储日志。这些数据结构支持按时间顺序存储和检索日志,且可以在O(log n)的时间复杂度内完成插入和查找操作。特别是,可以利用这些数据结构的范围查询功能,直接找到在特定时间范围内的所有日志,无需遍历整个数据结构。

相关问题

设计内存文件系统

设计内存文件系统