题目描述
力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡,安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次,这个系统会自动发布一个 警告 。
给你字符串数组 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 <= 105
- keyName.length == keyTime.length
- keyTime 格式为 "HH:MM" 。
- 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
- 1 <= keyName[i].length <= 10
- keyName[i] 只包含小写英文字母。
题目链接
题目难度——中等
方法一:排序+哈希表
要记录每个员工的用卡时间,我们就可以用一个字典来来存储,名字作为key,用卡时间列表为值,然后,我们对遍历这个字典,对每个员工来说,判断其有没有出现连续一小时内用卡的情况,有则加入答案,最后按序返回满足条件的名字。
其中需要注意可能的点,一是时间的处理我们要将小时化为分钟进行判断;二是在判断时不能判断每两个连续的时间点之间的时间差是否都是一小时之内,而应该判断连续的三个时间点最大和最小的时间时间的差是否在一小时内;三是题目并没有说明每个人的时间是按序给出的,所以我们要自己给每个人的时间排序。
代码/Python
class Solution:
def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
res = []
useTimes = defaultdict(list)
for name, time in zip(keyName, keyTime):
minute = int(time[3:])
hour = int(time[:2])
useTimes[name].append(hour * 60 + minute)
for name, time in useTimes.items():
n = len(time)
time.sort()
for i in range(1, n - 1):
if 0 <= time[i + 1] - time[i - 1] <= 60:
res.append(name)
break
return sorted(res)
排在前面的也是我这样写的,为什么我的就运行慢几十ms。
代码/C++
class Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
vector<string> res;
unordered_map<string, vector<int>> useTimes;
int len = keyName.size(), i, n, minute, hour;
for(i = 0; i < len; i++){
string name = keyName[i];
string time = keyTime[i];
minute = (time[3] - '0') * 10 + (time[4] - '0');
hour = (time[0] - '0') * 10 + (time[1] - '0');
useTimes[name].emplace_back(hour * 60 + minute);
}
for(auto &[name, time]: useTimes){
n = time.size();
sort(time.begin(), time.end());
for(i = 0; i < n - 2; i++){
if(time[i + 2] - time[i] >= 0 && time[i + 2] - time[i] <= 60){
res.emplace_back(name);
break;
}
}
}
sort(res.begin(), res.end());
return res;
}
};
总结
最慢的地方就是排序,所以时间复杂度是O(NlogN),空间是O(N),因为用到了字典。巧了,第一次做到和官方题解一样的思路和几乎一样的代码。