LeetCode-1604. 警告一小时内使用相同员工卡大于等于三次的人【哈希表，排序，数组】

题目描述：

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制 ，形如 “HH:MM” ，比方说 “23:51” 和 “09:49” 。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 “10:00” - “11:00” 视为一个小时时间范围内，而 “23:51” - “00:10” 不被视为一小时内，因为系统记录的是某一天内的使用情况。

示例 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”）。

示例 3：

输入：keyName = [“john”,“john”,“john”], keyTime = [“23:58”,“23:59”,“00:01”]
输出：[]

示例 4：

输入：keyName = [“leslie”,“leslie”,“leslie”,“clare”,“clare”,“clare”,“clare”], keyTime = [“13:00”,“13:20”,“14:00”,“18:00”,“18:51”,“19:30”,“19:49”]
输出：[“clare”,“leslie”]

提示：

1 <= keyName.length, keyTime.length <= 10^5
keyName.length == keyTime.length
keyTime 格式为 “HH:MM” 。
保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
1 <= keyName[i].length <= 10
keyName[i] 只包含小写英文字母。
https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/

解题思路一：时间转换成分钟数，直接解决跨天问题。用哈希表记录每个员工的名字以及对应的时间。然后遍历哈希表，对于每个员工，我们将该员工的所有打卡时间按照时间先后排序，然后遍历排序后的打卡时间，判断下标距离为2的两个时间是否在同一小时内，如果是，则将该员工加入答案数组。

因为是判断下标距离为2的两个时间，如果员工的打卡次数小于3，那么直接进入下层循环。（不用判断）

class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        unordered_map<string,vector<int>> d;//记录每个人对应的时间
        int n=keyName.size();
        for(int i=0;i<n;++i){
            string name=keyName[i];
            string time=keyTime[i];
            int hour=(time[0]-'0')*10+time[1];
            int minute=(time[3]-'0')*10+time[4];
            d[name].emplace_back(hour*60+minute);
        }
        vector<string> res;//记录最终名单
        for(auto&[name,list]:d){
            sort(list.begin(),list.end());//将该员工对应的时间进行排序
            int sz=list.size();
            for(int i=2;i<sz;++i)//i从2开始进行遍历，当sz<=2时进入下轮循环，即员工在一小时时间内使用员工卡的次数小于三次
                if(list[i]-list[i-2]<=60){
                    res.emplace_back(name);
                    break;
                }
        }
        sort(res.begin(),res.end());//按 字典序升序 排序后返回
        return res;
    }
};

时间复杂度：O(nlogn)//主要是排序
空间复杂度：O(n)//哈希表

解题思路二：0

解题思路三：0