Medium
题目描述
给你一个二维字符串数组 access_times，大小为 n。对于每个 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 <= 100access_times[i].length == 21 <= access_times[i][0].length <= 10access_times[i][0]只包含英文小写字母access_times[i][1].length == 4access_times[i][1]是24小时制时间格式access_times[i][1]只包含数字 ‘0’ 到 ‘9’
解题思路
这道题需要找出在一小时内访问系统三次或以上的员工。
解题思路：
数据分组：首先按员工姓名将访问时间分组，使用哈希表存储每个员工的所有访问时间。
时间转换：将时间字符串转换为分钟数便于计算。例如"0815"转换为8*60+15=495分钟。
排序处理：对每个员工的访问时间按分钟数排序，这样可以方便地检查连续时间段。
滑动窗口检查：对于每个员工，使用滑动窗口方法检查是否存在三个或以上访问时间在60分钟内。具体做法是：
- 遍历排序后的时间列表
- 对于每个时间点作为起始点，向后查找在60分钟内的所有时间点
- 如果找到3个或以上时间点，则该员工为高频访问员工
边界处理：注意题目要求恰好60分钟差距的时间不算在同一时间段内，所以判断条件是严格小于60分钟。
时间复杂度主要由排序决定，对于每个员工的访问记录排序。空间复杂度为存储分组数据的哈希表空间。
代码实现
class Solution {
public:
vector<string> findHighAccessEmployees(vector<vector<string>>& access_times) {
unordered_map<string, vector<int>> employeeAccess;
// 按员工分组并转换时间为分钟
for (auto& access : access_times) {
string name = access[0];
string time = access[1];
int minutes = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(2, 2));
employeeAccess[name].push_back(minutes);
}
vector<string> result;
// 检查每个员工
for (auto& [name, times] : employeeAccess) {
sort(times.begin(), times.end());
// 检查是否有三次或以上访问在60分钟内
for (int i = 0; i < times.size(); i++) {
int count = 1;
for (int j = i + 1; j < times.size(); j++) {
if (times[j] - times[i] < 60) {
count++;
if (count >= 3) {
result.push_back(name);
goto next_employee;
}
} else {
break;
}
}
}
next_employee:;
}
return result;
}
};
class Solution:
def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
from collections import defaultdict
# 按员工分组并转换时间为分钟
employee_access = defaultdict(list)
for name, time in access_times:
minutes = int(time[:2]) * 60 + int(time[2:])
employee_access[name].append(minutes)
result = []
# 检查每个员工
for name, times in employee_access.items():
times.sort()
# 检查是否有三次或以上访问在60分钟内
for i in range(len(times)):
count = 1
for j in range(i + 1, len(times)):
if times[j] - times[i] < 60:
count += 1
if count >= 3:
result.append(name)
break
else:
break
if count >= 3:
break
return result
public class Solution {
public IList<string> FindHighAccessEmployees(IList<IList<string>> access_times) {
var employeeAccess = new Dictionary<string, List<int>>();
// 按员工分组并转换时间为分钟
foreach (var access in access_times) {
string name = access[0];
string time = access[1];
int minutes = int.Parse(time.Substring(0, 2)) * 60 + int.Parse(time.Substring(2, 2));
if (!employeeAccess.ContainsKey(name)) {
employeeAccess[name] = new List<int>();
}
employeeAccess[name].Add(minutes);
}
var result = new List<string>();
// 检查每个员工
foreach (var kvp in employeeAccess) {
string name = kvp.Key;
var times = kvp.Value;
times.Sort();
// 检查是否有三次或以上访问在60分钟内
bool found = false;
for (int i = 0; i < times.Count && !found; i++) {
int count = 1;
for (int j = i + 1; j < times.Count; j++) {
if (times[j] - times[i] < 60) {
count++;
if (count >= 3) {
result.Add(name);
found = true;
break;
}
} else {
break;
}
}
}
}
return result;
}
}
var findHighAccessEmployees = function(access_times) {
const employeeAccess = new Map();
// 按员工分组并转换时间为分钟
for (const [name, time] of access_times) {
const minutes = parseInt(time.slice(0, 2)) * 60 + parseInt(time.slice(2));
if (!employeeAccess.has(name)) {
employeeAccess.set(name, []);
}
employeeAccess.get(name).push(minutes);
}
const result = [];
// 检查每个员工
for (const [name, times] of employeeAccess) {
times.sort((a, b) => a - b);
// 检查是否有三次或以上访问在60分钟内
let found = false;
for (let i = 0; i < times.length && !found; i++) {
let count = 1;
for (let j = i + 1; j < times.length; j++) {
if (times[j] - times[i] < 60) {
count++;
if (count >= 3) {
result.push(name);
found = true;
break;
}
} else {
break;
}
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × m × log m) | n为访问记录数，m为单个员工的最大访问次数，主要是排序的开销 |
| 空间复杂度 | O(n) | 用于存储按员工分组的访问时间数据 |