What is the primary approach to solving the High-Access Employees problem?

The primary approach involves sorting the access times for each employee and then applying a sliding window technique to check for three or more accesses within a one-hour period.

How can I efficiently track access times for each employee?

Using a hash map to store each employee's access times allows for quick lookups and more efficient scanning of access logs.

What is the time complexity of the High-Access Employees problem?

The time complexity is O(m * n log n), where n is the number of access records and m is the number of employees. This is due to sorting each employee's access times.

Can this problem be solved without sorting the access times?

Sorting is essential to ensure that the access times are properly aligned for the sliding window check. Without sorting, the problem cannot be solved efficiently.

What is the sliding window approach in this problem?

The sliding window approach checks whether three or more access times fall within any one-hour period by moving through the sorted list of times.

#2933

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

高访问员工

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

数组哈希表字符串排序

题目描述

给你一个长度为 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' 组成。

lightbulb

解题思路

方法一：哈希表 + 排序

我们用一个哈希表 $d$ 来存储每个员工的所有访问时间，其中键为员工的姓名，值为一个整数数组，表示该员工的所有访问时间，该时间为从当天 00:00 开始的分钟数。

对于每个员工，我们将其所有访问时间按照从小到大的顺序进行排序。然后我们遍历该员工的所有访问时间，如果存在连续的三个访问时间 $t_1, t_2, t_3$ ，满足 $t_3 - t_1 < 60$ ，则该员工为高访问员工，我们将其姓名加入答案数组中。

最后，返回答案数组即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为访问记录的数量。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates who suggest sorting followed by a sliding window approach demonstrate good problem-solving skills.
question_mark
If the candidate suggests inefficient brute force solutions without focusing on sorting or efficient lookups, it indicates a lack of optimization awareness.
question_mark
A strong candidate will mention using hash tables or maps for faster access time lookups.

warning

常见陷阱

外企场景

error
Failing to sort the access times for each employee, leading to incorrect results.
error
Not recognizing that access times need to be evaluated within a one-hour window for each employee.
error
Not efficiently managing the access logs using appropriate data structures, which could lead to excessive time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider scenarios where access logs are already sorted or partially sorted.
arrow_right_alt
Challenge with larger datasets where optimizing sorting and lookup times becomes crucial.
arrow_right_alt
Handle cases where multiple employees have similar access times, requiring precise detection of overlaps.

help

常见问题

外企场景

继续练习

#3035 回文字符串的最大数量 #3143 正方形中的最多点数 #2512 奖励最顶尖的 K 名学生