警告一小时内使用相同员工卡大于等于三次的人【LC1604】
LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.
You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.
Access times are given in the 24-hour time format “HH:MM”, such as "23:51" and "09:49".
Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.
Notice that "10:00" - "11:00" is considered to be within a one-hour period, while "22:51" - "23:52" is not considered to be within a one-hour period.
2023/2/7
- 思路：
。使用哈希表统计每位员工使用工卡的所有时间节点，将时间转化为分钟的形式，方便后续统计一小时内使用次数大于等于3的员工
。然后将每位员工的时间节点从小到大排序，如果在60分钟的间隔内，有大于等于3个时间节点，那么需要对该员工发出警告
- 双指针滑动窗口统计
- 枚举每一个时间节点i ii，判断其与第i−1个时间节点的差值是否小于等于60
。返回结果需要按照字典顺序排序
- 实现
class Solution { public List<String> alertNames(String[] keyName, String[] keyTime) { Map<String,List<Integer>> map = new HashMap<>();; List<String> res = new LinkedList<>(); int n = keyName.length; for (int i = 0; i < n; i++){ String name = keyName[i]; String[] times = keyTime[i].split(":"); int hour = Integer.parseInt(times[0]); int m = Integer.parseInt(times[1]); int t = hour * 60 + m; List<Integer> list = map.getOrDefault(name, new ArrayList<>()); list.add(t); map.put(name, list); } for (var node : map.entrySet()){ String name = node.getKey(); List<Integer> times = node.getValue(); int size = times.size(); Collections.sort(times); // 滑动窗口 // if (size < 3) continue; // int l = 0, r = 0; // while (l < size && r < size){ // while (r < size && times.get(r) - times.get(l) <= 60 ){ // r++; // } // if (r - l >= 3){ // res.add(name); // break; // } // while (l < size && r < size && times.get(r) - times.get(l) > 60){ // l++; // } // } // 枚举 for (int i = 2; i < size; i++){ if (times.get(i) - times.get(i - 2) <= 60){ res.add(name); break; } } } Collections.sort(res); return res; } }
。复杂度
- 时间复杂度：O ( n l o g n )
- 空间复杂度：O ( n )
