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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

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

方法一：哈希表 + 排序

由于给定的数组是每个员工在同一天内使用员工卡的时间，因此同一个员工使用员工卡的时间顺序一定是按照小时数和分钟数递增的。只要获得每个员工的全部使用员工卡的时间，即可判断哪些员工收到系统警告，即哪些员工在一小时内使用员工卡的次数大于等于三次。

遍历数组 keyName 和 keyTime，即可获得每个员工的全部使用员工卡的时间列表。使用哈希表记录每个员工的全部使用员工卡的时间列表。为了方便后序计算，将使用员工卡的时间转成分钟数。

获得每个员工的全部使用员工卡的时间列表之后，再对每个员工分别判断是否收到系统警告。具体做法是，对于每个员工，从哈希表中获得该员工的全部使用员工卡的时间列表，并将列表排序，然后遍历排序后的列表。如果发现列表中存在三个连续元素中的最大元素与最小元素之差不超过 60，即意味着这三次使用员工卡是在一小时之内发生的，因此因此该员工会收到系统警告。由于只需要知道每个员工是否收到系统警告，因此一旦可以确认某个员工会收到系统警告，即可停止遍历该员工的剩余的使用员工卡的时间。

使用一个列表存储收到系统警告的员工名字。在得到所有的收到系统警告的员工名字之后，对该列表进行排序，然后返回。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        timeMap = defaultdict(list)
        for name, time in zip(keyName, keyTime):
            hour, minute = int(time[:2]), int(time[3:])
            timeMap[name].append(hour * 60 + minute)

        ans = []
        for name, times in timeMap.items():
            times.sort()
            if any(t2 - t1 <= 60 for t1, t2 in zip(times, times[2:])):
                ans.append(name)
        ans.sort()
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String, List<Integer>> timeMap = new HashMap<String, List<Integer>>();
        int n = keyName.length;
        for (int i = 0; i < n; i++) {
            String name = keyName[i];
            String time = keyTime[i];
            timeMap.putIfAbsent(name, new ArrayList<Integer>());
            int hour = (time.charAt(0) - '0') * 10 + (time.charAt(1) - '0');
            int minute = (time.charAt(3) - '0') * 10 + (time.charAt(4) - '0');
            timeMap.get(name).add(hour * 60 + minute);
        }
        List<String> res = new ArrayList<String>();
        Set<String> keySet = timeMap.keySet();
        for (String name : keySet) {
            List<Integer> list = timeMap.get(name);
            Collections.sort(list);
            int size = list.size();
            for (int i = 2; i < size; i++) {
                int time1 = list.get(i - 2), time2 = list.get(i);
                int difference = time2 - time1;
                if (difference <= 60) {
                    res.add(name);
                    break;
                }
            }
        }
        Collections.sort(res);
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public IList<string> AlertNames(string[] keyName, string[] keyTime) {
        IDictionary<string, IList<int>> timeDictionary = new Dictionary<string, IList<int>>();
        int n = keyName.Length;
        for (int i = 0; i < n; i++) {
            string name = keyName[i];
            string time = keyTime[i];
            timeDictionary.TryAdd(name, new List<int>());
            int hour = (time[0] - '0') * 10 + (time[1] - '0');
            int minute = (time[3] - '0') * 10 + (time[4] - '0');
            timeDictionary[name].Add(hour * 60 + minute);
        }
        IList<string> res = new List<string>();
        foreach (KeyValuePair<string, IList<int>> pair in timeDictionary) {
            string name = pair.Key;
            IList<int> list = pair.Value;
            ((List<int>) list).Sort();
            int size = list.Count;
            for (int i = 2; i < size; i++) {
                int time1 = list[i - 2], time2 = list[i];
                int difference = time2 - time1;
                if (difference <= 60) {
                    res.Add(name);
                    break;
                }
            }
        }
        ((List<string>) res).Sort();
        return res;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        unordered_map<string, vector<int>> timeMap;
        int n = keyName.size();
        for (int i = 0; i < n; i++) {
            string name = keyName[i];
            string time = keyTime[i];
            int hour = (time[0] - '0') * 10 + (time[1] - '0');
            int minute = (time[3] - '0') * 10 + (time[4] - '0');
            timeMap[name].emplace_back(hour * 60 + minute);
        }
        vector<string> res;
        for (auto &[name, list] : timeMap) {
            sort(list.begin(), list.end());
            int size = list.size();
            for (int i = 2; i < size; i++) {
                int time1 = list[i - 2], time2 = list[i];
                int difference = time2 - time1;
                if (difference <= 60) {
                    res.emplace_back(name);
                    break;
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
typedef struct {
    char *key;
    struct ListNode *val;
    UT_hash_handle hh;
} HashItem; 

struct ListNode *creatListNode(int val) {
    struct ListNode *obj = (struct ListNode *)malloc(sizeof(struct ListNode));
    obj->val = val;
    obj->next = NULL;
    return obj;
}

HashItem *hashFindItem(HashItem **obj, const char * key) {
    HashItem *pEntry = NULL;
    HASH_FIND_STR(*obj, key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, const char *key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = key;
        pEntry->val = NULL;
        HASH_ADD_STR(*obj, key, pEntry);
    } 
    struct ListNode *node = creatListNode(val);
    node->next = pEntry->val;
    pEntry->val = node;
    return true;
}

void freeList(struct ListNode *list) {
    while (list) {
        struct ListNode *curr = list;
        list = list->next;
        free(curr);
    }
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);
        freeList(curr->val);
        free(curr);             
    }
}

static int cmp1(const void *pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

static int cmp2(const void *pa, const void *pb) {
    return strcmp(*(char **)pa, *(char **)pb);
}

char ** alertNames(char ** keyName, int keyNameSize, char ** keyTime, int keyTimeSize, int* returnSize) {
    HashItem *timeMap = NULL;
    for (int i = 0; i < keyNameSize; i++) {
        char *name = keyName[i];
        char *time = keyTime[i];
        int hour = (time[0] - '0') * 10 + (time[1] - '0');
        int minute = (time[3] - '0') * 10 + (time[4] - '0');
        hashAddItem(&timeMap, name, hour * 60 + minute);
    }

    char **res = (char **)malloc(sizeof(char *) * keyNameSize);
    int pos = 0;
    HashItem *curr = NULL, *temp = NULL;
    int arr[keyNameSize];
    HASH_ITER(hh, timeMap, curr, temp) {
        int size = 0;
        for (struct ListNode *node = curr->val; node; node = node->next) {
            arr[size++] = node->val;
        }
        qsort(arr, size, sizeof(int), cmp1); 
        for (int i = 2; i < size; i++) {
            int time1 = arr[i - 2], time2 = arr[i];
            int difference = time2 - time1;
            if (difference <= 60) {
                res[pos] = (char *)malloc(sizeof(char) * (strlen(curr->key) + 1));
                strcpy(res[pos], curr->key);
                pos++;
                break;
            }
        }
    }
    qsort(res, pos, sizeof(char *), cmp2);
    *returnSize = pos;
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var alertNames = function(keyName, keyTime) {
    const timeMap = new Map();
    const n = keyName.length;
    for (let i = 0; i < n; i++) {
        const name = keyName[i];
        const time = keyTime[i];
        if (!timeMap.has(name)) {
            timeMap.set(name, []);
        }
        const hour = (time[0].charCodeAt() - '0'.charCodeAt()) * 10 + (time[1].charCodeAt() - '0'.charCodeAt());
        const minute = (time[3].charCodeAt() - '0'.charCodeAt()) * 10 + (time[4].charCodeAt() - '0'.charCodeAt());
        timeMap.get(name).push(hour * 60 + minute);
    }
    let res = [];
    const keySet = timeMap.keys();
    for (const name of keySet) {
        const list = timeMap.get(name);
        list.sort((a, b) => a - b);
        const size = list.length;
        for (let i = 2; i < size; i++) {
            const time1 = list[i - 2], time2 = list[i];
            const difference = time2 - time1;
            if (difference <= 60) {
                res.push(name);
                break;
            }
        }
    }
    res.sort();
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func alertNames(keyName, keyTime []string) (ans []string) {
    timeMap := map[string][]int{}
    for i, name := range keyName {
        t := keyTime[i]
        hour := int(t[0]-'0')*10 + int(t[1]-'0')
        minute := int(t[3]-'0')*10 + int(t[4]-'0')
        timeMap[name] = append(timeMap[name], hour*60+minute)
    }
    for name, times := range timeMap {
        sort.Ints(times)
        for i, t := range times[2:] {
            if t-times[i] <= 60 {
                ans = append(ans, name)
                break
            }
        }
    }
    sort.Strings(ans)
    return
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 keyName 和 keyTime 的长度。
    需要遍历数组 keyName 和 keyTime，得到每个员工的全部使用员工卡的时间，遍历的时间复杂度是 O(n)，存入哈希表的时间复杂度是 O(1)，因此时间复杂度是 O(n)。
    然后判断每个员工是否收到系统警告，需要进行排序和遍历的操作，最坏情况下，排序的时间复杂度是 O(n \log n)，遍历的时间复杂度是 O(n)，因此时间复杂度是 O(n \log n)。
    因此总时间复杂度是 O(n \log n)。

  • 空间复杂度：O(n)，其中 n 是数组 keyName 和 keyTime 的长度。空间复杂度主要取决于哈希表，需要存储所有员工的全部打卡时间。

 Comments
On this page
1604-警告一小时内使用相同员工卡大于等于三次的人