Medium

题目描述

LeetCode 公司的员工使用钥匙卡解锁办公室门。每当员工使用钥匙卡时，安全系统都会保存员工的姓名和使用时间。如果任何员工在一小时内使用钥匙卡三次或以上，系统会发出警报。

给定字符串列表 keyName 和 keyTime，其中 [keyName[i], keyTime[i]] 对应一个人的姓名和他们在一天中使用钥匙卡的时间。

访问时间以 24 小时时间格式 “HH:MM” 给出，如 “23:51” 和 “09:49”。

返回收到频繁使用钥匙卡警报的唯一员工姓名列表。按字母升序排列姓名。

注意 “10:00” - “11:00” 被认为是在一小时内，而 “22:51” - “23:52” 不被认为是在一小时内。

示例 1：

输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了钥匙卡 3 次（"10:00","10:40", "11:00"）。

示例 2：

输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了钥匙卡 3 次（"21:00","21:20", "21:30"）。

约束：

  • 1 <= keyName.length, keyTime.length <= 10^5
  • keyName.length == keyTime.length
  • keyTime[i] 格式为 “HH:MM”
  • [keyName[i], keyTime[i]] 是唯一的
  • 1 <= keyName[i].length <= 10
  • keyName[i] 只包含小写英文字母

解题思路

这道题的关键是检测每个员工是否在任意一小时内使用钥匙卡三次或以上。

解题思路：

  1. 数据预处理：首先需要将时间字符串转换为分钟数，便于计算时间差。同时按员工姓名分组收集使用时间。

  2. 排序：对每个员工的使用时间进行排序，这样可以使用滑动窗口技术来检查连续的时间段。

  3. 滑动窗口检查：对于每个员工的已排序时间列表，使用滑动窗口来检查是否存在三个或以上的使用记录在60分钟内。具体做法是：

    • 维护一个窗口，窗口内的时间差不超过60分钟
    • 当窗口内有3个或以上记录时，该员工需要被警报
    • 移动窗口直到检查完所有时间点

  4. 结果处理：收集所有需要警报的员工姓名，并按字母顺序排序返回。

时间复杂度优化：通过哈希表分组和排序，避免了暴力枚举所有时间对的方法，将复杂度从O(n³)优化到O(n log n)。

代码实现

class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        unordered_map<string, vector<int>> timeMap;
        
        // Convert time to minutes and group by name
        for (int i = 0; i < keyName.size(); i++) {
            string time = keyTime[i];
            int hour = stoi(time.substr(0, 2));
            int minute = stoi(time.substr(3, 2));
            int totalMinutes = hour * 60 + minute;
            timeMap[keyName[i]].push_back(totalMinutes);
        }
        
        vector<string> result;
        
        for (auto& entry : timeMap) {
            vector<int>& times = entry.second;
            sort(times.begin(), times.end());
            
            // Check for 3 or more uses within 60 minutes
            for (int i = 0; i <= (int)times.size() - 3; i++) {
                if (times[i + 2] - times[i] <= 60) {
                    result.push_back(entry.first);
                    break;
                }
            }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        from collections import defaultdict
        
        time_map = defaultdict(list)
        
        # Convert time to minutes and group by name
        for i in range(len(keyName)):
            time_str = keyTime[i]
            hour = int(time_str[:2])
            minute = int(time_str[3:])
            total_minutes = hour * 60 + minute
            time_map[keyName[i]].append(total_minutes)
        
        result = []
        
        for name, times in time_map.items():
            times.sort()
            
            # Check for 3 or more uses within 60 minutes
            for i in range(len(times) - 2):
                if times[i + 2] - times[i] <= 60:
                    result.append(name)
                    break
        
        return sorted(result)

public class Solution {
    public IList<string> AlertNames(string[] keyName, string[] keyTime) {
        var timeMap = new Dictionary<string, List<int>>();
        
        // Convert time to minutes and group by name
        for (int i = 0; i < keyName.Length; i++) {
            string time = keyTime[i];
            int hour = int.Parse(time.Substring(0, 2));
            int minute = int.Parse(time.Substring(3, 2));
            int totalMinutes = hour * 60 + minute;
            
            if (!timeMap.ContainsKey(keyName[i])) {
                timeMap[keyName[i]] = new List<int>();
            }
            timeMap[keyName[i]].Add(totalMinutes);
        }
        
        var result = new List<string>();
        
        foreach (var entry in timeMap) {
            var times = entry.Value;
            times.Sort();
            
            // Check for 3 or more uses within 60 minutes
            for (int i = 0; i <= times.Count - 3; i++) {
                if (times[i + 2] - times[i] <= 60) {
                    result.Add(entry.Key);
                    break;
                }
            }
        }
        
        result.Sort();
        return result;
    }
}

var alertNames = function(keyName, keyTime) {
    const timeMap = new Map();
    
    // Convert time to minutes and group by name
    for (let i = 0; i < keyName.length; i++) {
        const time = keyTime[i];
        const hour = parseInt(time.substring(0, 2));
        const minute = parseInt(time.substring(3, 5));
        const totalMinutes = hour * 60 + minute;
        
        if (!timeMap.has(keyName[i])) {
            timeMap.set(keyName[i], []);
        }
        timeMap.get(keyName[i]).push(totalMinutes);
    }
    
    const result = [];
    
    for (const [name, times] of timeMap) {
        times.sort((a, b) => a - b);
        
        // Check for 3 or more uses within 60 minutes
        for (let i = 0; i <= times.length - 3; i++) {
            if (times[i + 2] - times[i] <= 60) {
                result.push(name);
                break;
            }
        }
    }
    
    return result.sort();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解O(n log n)O(n)
  • 时间复杂度：O(n log n)，其中 n 是输入的长度。主要耗时在对每个员工的时间列表进行排序
  • 空间复杂度：O(n)，用于存储哈希表中的员工姓名和对应的时间列表