跳到主要内容

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

· 阅读需 4 分钟

1、题干​

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

给你字符串数组 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] 只包含小写英文字母。

2、思路1​

哈希表存储员工姓名（键）和开门时间数组（值），时间转为分钟数并排序，最后检查每个员工的开门时间是否违规

3、代码​

function alertNames(names: string[], times: string[]): string[] {
    const map = new Map<string, number[]>();
    for (let i = 0; i < names.length; i++) {
        if (!map.has(names[i])) map.set(names[i], []);
        map.get(names[i]).push(60 * (+times[i].slice(0, 2)) + +(times[i].slice(3)));
    }

    const ans = [];
    for (const [name, minutes] of map) {
        if (minutes.length < 3) continue;

        minutes.sort((a, b) => a - b);
        for (let i = 0; i < minutes.length - 2 && ans.at(-1) !== name; i++) {
            if (minutes[i + 2] - minutes[i] <= 60) ans.push(name);
        }
    }

    return ans.sort();
};

4、复杂度​

  • 时间复杂度：O(n∗logn)O(n*logn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png

6、思路2​

二维数组存储员工姓名和开门时间，时间转为分钟数，对二维数组按姓名和分钟数升序排序，最后检查每个员工的开门时间是否违规

7、代码​

function alertNames(names: string[], times: string[]): string[] {
    const matrix: [string, number][] = names.map((n, i) => [n, 60 * (+times[i].slice(0, 2)) + +(times[i].slice(3))]);
    matrix.sort((a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return a[0] > b[0] ? 1 : -1;
    });

    const ans = [];

    for (let i = 0; i < matrix.length - 2; i++) {
        if (matrix[i + 2][0] !== matrix[i][0] || matrix[i][0] === ans.at(-1)) continue;
        if (matrix[i + 2][1] - matrix[i][1] <= 60) ans.push(matrix[i][0]);
    }

    return ans;
};

8、复杂度​

  • 时间复杂度：O(n∗logn)O(n*logn)
  • 空间复杂度：O(n)O(n)

9、执行结果​

image.png