警告一小时内使用相同员工卡大于等于三次的人

标签: 数组 哈希表 字符串 排序

难度: Medium

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "22:51" - "23:52" 不被视为一小时时间范围内。

示例 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"）。

提示：

  • 1 <= keyName.length, keyTime.length <= 105
  • keyName.length == keyTime.length
  • keyTime 格式为 "HH:MM" 。
  • 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
  • 1 <= keyName[i].length <= 10
  • keyName[i] 只包含小写英文字母。

Submission

运行时间: 137 ms

内存: 37.9 MB

def getCount(time: str) -> int:
    h = (ord(time[0]) - ord('0')) * 10 + ord(time[1]) - ord('0')
    h *= 60
    m = (ord(time[3]) - ord('0')) * 10 + ord(time[4]) - ord('0')
    return h + m
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        record = {}
        n = len(keyName)
        for i in range(n):
            name, time = keyName[i], keyTime[i]
            if name not in record:
                record[name] = []
            record[name].append(getCount(time))
        ans = []
        for name, time in record.items():
            time.sort()
            for i in range(2, len(time)):
                if time[i] - time[i - 2] <= 60:
                    ans.append(name)
                    break
        ans.sort()
        return ans

Explain

解题思路主要包括以下几个步骤：1. 创建一个哈希表 `record`，以每个员工的名字为键，以该员工所有使用卡片的时间（以分钟为单位转换后的整数列表）为值。2. 使用辅助函数 `getCount` 将时间从 'HH:MM' 格式转换为从午夜开始的总分钟数。3. 遍历每个员工的使用时间记录，首先对时间进行排序，然后使用滑动窗口的方式检查任意连续三次使用是否在一小时（60分钟）内。如果是，则该员工的名字被添加到答案列表中。4. 最后，对答案列表进行排序并返回。

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

空间复杂度: O(n)

def getCount(time: str) -> int:
    # 将时间从'HH:MM'格式转换为从午夜起的分钟数
    h = (ord(time[0]) - ord('0')) * 10 + ord(time[1]) - ord('0')
    h *= 60 # 转换小时为分钟
    m = (ord(time[3]) - ord('0')) * 10 + ord(time[4]) - ord('0')
    return h + m
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        record = {} # 字典存储每个员工的使用时间记录
        n = len(keyName)
        for i in range(n):
            name, time = keyName[i], keyTime[i]
            if name not in record:
                record[name] = []
            record[name].append(getCount(time))
        ans = [] # 存储结果的列表
        for name, time in record.items():
            time.sort() # 对时间进行排序
            for i in range(2, len(time)):
                if time[i] - time[i - 2] <= 60: # 检查是否有三次使用在一小时内
                    ans.append(name)
                    break
        ans.sort() # 对结果按字典序排序
        return ans

Explore

这个逻辑背后的原理基于滑动窗口的思想。在一个已经按时间排序的列表中，如果你想检验任意连续的三个时间点是否在60分钟内，只需要检查这三个时间点的最大值和最小值的差。由于列表是排序的，对于连续的三个时间点time[i-2], time[i-1], time[i]（其中i >= 2），time[i]总是最大值，而time[i-2]是最小值。因此，只需要检查time[i]和time[i-2]的差是否不超过60分钟。如果这两个时间点的差不超过60分钟，显然中间的time[i-1]也会落在这个范围内，满足连续的三个时间点都在60分钟内的条件。

在这个题解的逻辑中，一旦一个员工的名字被检测到满足条件并被添加到答案列表中，就会立即使用`break`跳出循环，停止对该员工的进一步检测。这意味着每个员工的名字只有在首次被发现满足条件时会被添加到答案列表中，后续即便有其他满足条件的时间段也不会再次检测或添加。因此，答案列表不会包含重复的名字。