高访问员工

难度: Medium

给你一个长度为 n 、下标从 0 开始的二维字符串数组 access_times 。对于每个 i（0 <= i <= n - 1 ），access_times[i][0] 表示某位员工的姓名，access_times[i][1] 表示该员工的访问时间。access_times 中的所有条目都发生在同一天内。

访问时间用四位数字表示，符合 24 小时制 ，例如 "0800" 或 "2250" 。

如果员工在 同一小时内 访问系统 三次或更多 ，则称其为 高访问 员工。

时间间隔正好相差一小时的时间不被视为同一小时内。例如，"0815" 和 "0915" 不属于同一小时内。

一天开始和结束时的访问时间不被计算为同一小时内。例如，"0005" 和 "2350" 不属于同一小时内。

以列表形式，按任意顺序，返回所有 高访问 员工的姓名。

示例 1：

输入：access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
输出：["a"]
解释："a" 在时间段 [05:32, 06:31] 内有三条访问记录，时间分别为 05:32 、05:49 和 06:21 。
但是 "b" 的访问记录只有两条。
因此，答案是 ["a"] 。

示例 2：

输入：access_times = [["d","0002"],["c","0808"],["c","0829"],["e","0215"],["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
输出：["c","d"]
解释："c" 在时间段 [08:08, 09:07] 内有三条访问记录，时间分别为 08:08 、08:09 和 08:29 。
"d" 在时间段 [14:10, 15:09] 内有三条访问记录，时间分别为 14:10 、14:44 和 15:08 。
然而，"e" 只有一条访问记录，因此不能包含在答案中，最终答案是 ["c","d"] 。

示例 3：

输入：access_times = [["cd","1025"],["ab","1025"],["cd","1046"],["cd","1055"],["ab","1124"],["ab","1120"]]
输出：["ab","cd"]
解释："ab"在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、11:20 和 11:24 。
"cd" 在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、10:46 和 10:55 。
因此，答案是 ["ab","cd"] 。

提示：

1 <= access_times.length <= 100
access_times[i].length == 2
1 <= access_times[i][0].length <= 10
access_times[i][0] 仅由小写英文字母组成。
access_times[i][1].length == 4
access_times[i][1] 采用24小时制表示时间。
access_times[i][1] 仅由数字 '0' 到 '9' 组成。

Submission

运行时间: 42 ms

内存: 16.0 MB

class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        n_t = defaultdict(list)
        for name, s in access_times:
            t = int(s[:2]) * 60 + int(s[2:])
            n_t[name].append(t)
        
        ans = []
        for name, t in n_t.items():
            t.sort()
            if any(t[i] - t[i - 2] < 60 for i in range(2, len(t))):
                ans.append(name)
        return ans

Explain

首先，将每个员工的访问时间转换为分钟数，并使用哈希表将相同员工的访问时间归类到一起。然后，对每个员工的访问时间进行排序，以便我们可以按顺序检查时间间隔。接下来，我们检查每个员工的访问时间列表，如果在列表中存在任意连续三个时间点，它们的时间差小于60分钟，则将该员工视为高访问员工，并将其姓名添加到结果列表中。最后，返回结果列表。

时间复杂度: O(n log n)

空间复杂度: O(n)

from collections import defaultdict

class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        n_t = defaultdict(list)
        for name, s in access_times:
            t = int(s[:2]) * 60 + int(s[2:])  # Convert access time to minutes
            n_t[name].append(t)
        
        ans = []
        for name, t in n_t.items():
            t.sort()
            if any(t[i] - t[i - 2] < 60 for i in range(2, len(t))):  # Check if any three consecutive times are within the same hour
                ans.append(name)
        return ans

Explore

这个条件通过检查员工的任意连续三个访问时间点是否相差少于60分钟来实现。首先，所有访问时间都被转换成分钟，并按时间顺序排序。然后，使用`range(2, len(t))`遍历时间列表，确保我们始终查看三个连续的时间点（i, i-1, i-2）。如果这三个时间点中最早和最晚的时间差小于60分钟，即`t[i] - t[i - 2] < 60`，则意味着这三个时间点在同一小时内。这样可以确保只要有任意三个连续访问时间满足这个条件，就可以将该员工标记为高访问员工。

在当前的实现中，并没有特别处理同一分钟内多次访问的情况。算法将所有访问时间转换为分钟后，如果一个员工在同一分钟内多次访问，这些访问会记录为相同的时间点。由于算法检查的是任意连续三个时间点的时间差，因此即使是在同一分钟内的三次访问也会被识别，并将该员工视为高访问员工。这意味着即使多次访问发生在同一分钟，也满足`any(t[i] - t[i - 2] < 60 for i in range(2, len(t)))`的条件，因为差值会是0。