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

题目描述

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

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

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

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

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。

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

示例 3：

输入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
输出：[]

示例 4：

输入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
输出：["clare","leslie"]

提示：

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

思路

从时间复杂度，解题思路及题目特点，数据结构选择这三个方面进行解析

时间复杂度

根据提示，输入的数据量在10^5，可以预估到最后的整体的时间复杂度最大是nLgn。所以这边可以将排序，优先级队列等nLg复杂的的算法和数据结构作为备选。

题目特点及解题思路

从题目的类容看来，这道题偏向业务代码，使用语言的API可以更方便的实现。

题目的一个输入是时间，数据格式是字符串，映射的格式是HH:MM，我们可以将这个数据转换为int类型，可以方便的简化计算。

题目的输出是一个去重后的List，所以我们可以使用一个Map去存储keyName和其对应的时间，然后我们对每个keyName进行判断，如果一个小时内超过了3次，就将该keyName存储到答案中。

数据结构选择

根据上面的分析，我们需要一个保存答案的List，一个存储keyName和其对应时间的Map.

题解

class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String,List<Integer>> map=new HashMap<>();
        int n=keyName.length;
        for(int i=0;i<n;i++){
            String s=keyTime[i];
            int time=((s.charAt(0)-'0')*10+(s.charAt(1)-'0'))*60+((s.charAt(3)-'0')*10+(s.charAt(4)-'0'));
            if(map.containsKey(keyName[i])){
                map.get(keyName[i]).add(time);
            }
            else{
                List<Integer> one=new ArrayList<>();
                one.add(time);
                map.put(keyName[i],one);
            }
        }
        List<String> ans=new ArrayList<>();
        for(String item:map.keySet()){
            List<Integer> one=map.get(item);
            Collections.sort(one);
            int m=one.size();
            for(int i=1;i<m-1;i++){
                int before=one.get(i-1);
                int after=one.get(i+1);
                if(after-before<=60){
                    ans.add(item);
                    break;
                }
            }
        }
        Collections.sort(ans);
        return ans;
    }
}