leetcode 3433. 统计用户被提及情况 中等

给你一个整数numberOfUsers表示用户总数，另有一个大小为n x 3的数组events。

每个events[i]都属于下述两种类型之一：

1. 消息事件（Message Event）：["MESSAGE", "timestampi", "mentions_stringi"]
   • 事件表示在timestampi时，一组用户被消息提及。
   • mentions_stringi字符串包含下述标识符之一：
     • id<number>：其中<number>是一个区间[0,numberOfUsers - 1]内的整数。可以用单个空格分隔多个id ，并且 id 可能重复。此外，这种形式可以提及离线用户。
     • ALL：提及所有用户。
     • HERE：提及所有在线用户。
2. 离线事件（Offline Event）：["OFFLINE", "timestampi", "idi"]
   • 事件表示用户idi在timestampi时变为离线状态60 个单位时间。用户会在timestampi + 60时自动再次上线。

返回数组mentions，其中mentions[i]表示 id 为i的用户在所有MESSAGE事件中被提及的次数。

最初所有用户都处于在线状态，并且如果某个用户离线或者重新上线，其对应的状态变更将会在所有相同时间发生的消息事件之前进行处理和同步。

注意在单条消息中，同一个用户可能会被提及多次。每次提及都需要被分别统计。

示例 1：

输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]

输出：[2,2]

解释：

最初，所有用户都在线。

时间戳 10 ，id1和id0被提及，mentions = [1,1]

时间戳 11 ，id0离线。

时间戳 71 ，id0再次上线并且"HERE"被提及，mentions = [2,2]

示例 2：

输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]

输出：[2,2]

解释：

最初，所有用户都在线。

时间戳 10 ，id1和id0被提及，mentions = [1,1]

时间戳 11 ，id0离线。

时间戳 12 ，"ALL"被提及。这种方式将会包括所有离线用户，所以id0和id1都被提及，mentions = [2,2]

示例 3：

输入：numberOfUsers = 2, events = [["OFFLINE","10","0"],["MESSAGE","12","HERE"]]

输出：[0,1]

解释：

最初，所有用户都在线。

时间戳 10 ，id0离线。

时间戳 12 ，"HERE"被提及。由于id0仍处于离线状态，其将不会被提及，mentions = [0,1]

提示：

• 1 <= numberOfUsers <= 100
• 1 <= events.length <= 100
• events[i].length == 3
• events[i][0]的值为MESSAGE或OFFLINE。
• 1 <= int(events[i][1]) <= 10^5
• 在任意"MESSAGE"事件中，以id<number>形式提及的用户数目介于1和100之间。
• 0 <= <number> <= numberOfUsers - 1
• 题目保证OFFLINE引用的用户 id 在事件发生时处于在线状态。

分析：先将所有的事件按照发生时间从小到大排序，时间相同的事件，离线排在消息前面处理。同时用一个数组 flag 标识用户是否在线。初始时 flag 全为 -1，代表所有用户都在线；接着当遇到离线事件时，将离线用户 i 的 flag[i] 改为对应 times+60，表示用户 i 在 times+60 这个时间及之后在线。排序后遍历所有的消息，按照题目要求进行记录即可。

/** * Note: The returned array must be malloced, assume caller calls free(). */ typedef struct node { int ind,times; char type; }node; int cmp(const void *a,const void *b) { node *aa=a; node *bb=b; if(aa->times!=bb->times) return aa->times-bb->times; if(aa->type!=bb->type) return bb->type-aa->type; return aa->ind-bb->ind; } int* countMentions(int numberOfUsers, char*** events, int eventsSize, int* eventsColSize, int* returnSize) { int *ans=(int*)malloc(sizeof(int)*(numberOfUsers+5));*returnSize=numberOfUsers; int flag[numberOfUsers+5]; node temp[eventsSize+5]; for(int i=0;i<numberOfUsers;++i) ans[i]=0,flag[i]=-1; for(int i=0;i<eventsSize;++i) { temp[i].ind=i,temp[i].type=events[i][0][0]; temp[i].times=0; for(int j=0;events[i][1][j];++j) temp[i].times=temp[i].times*10+events[i][1][j]-'0'; } qsort(temp,eventsSize,sizeof(node),cmp); for(int i=0;i<eventsSize;++i) { int pos=temp[i].ind,times=temp[i].times; if(events[pos][0][0]=='M') { if(events[pos][2][0]=='A') { for(int j=0;j<numberOfUsers;++j) ans[j]++; } else if(events[pos][2][0]=='H') { for(int j=0;j<numberOfUsers;++j) { if(flag[j]==-1||flag[j]<=times) ans[j]++; } } else { int id=0; for(int j=2;events[pos][2][j];++j) { if(events[pos][2][j]==' ') ans[id]++,id=0; else if(events[pos][2][j]>='0'&&events[pos][2][j]<='9') id=id*10+events[pos][2][j]-'0'; else continue; } ans[id]++,id=0; } } else { int id=0; for(int j=0;events[pos][2][j];++j) { if(events[pos][2][j]==' ') flag[id]=times+60,id=0; else if(events[pos][2][j]>='0'&&events[pos][2][j]<='9') id=id*10+events[pos][2][j]-'0'; else continue; } flag[id]=times+60,id=0; } } return ans; }