字节 根据日志求用户在线峰值与持续时长 题解，面试后复盘。

题目

根据日志求用户在线峰值与持续时长

已知一天内用户登录登出的日志（数据量较大），求这一天用户在线的最大峰值和持续时长​

  • 日志包含字段（userid, login_time, logout_time）​
  • 登录登出时间精确到秒

粗暴解

思路

使用一个有序map存储：时刻->用户在线数。

遍历入参日志数组，更新时间段对应用户在线数。

缺陷：需根据login_time, logout_time区间再有一个range长度的循环，并且存在重复计算。

代码

 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

private boolean continuous(int i, int j) {
      return i == j + 1 || i == j - 1;
}

static class Log {
      int userId;

      int loginTime;

      int logoutTime;
}

public int[] calculateActiveUserPeakAndLastingTimeBF(Log[] logs) {
      // O(n^2)
      // 遍历当前日志range：当前时刻在线人数 叠加
      Map<Integer, Integer> second2Cnt = new LinkedHashMap<>();
      for (Log log : logs) {
      int loginTime = log.loginTime;
      int logoutTime = log.logoutTime;
      // 遍历每一秒
      for (int second = loginTime; second <= logoutTime; second++) {
            second2Cnt.put(second, second2Cnt.getOrDefault(second, 0) + 1);
      }
      }

      int[] ans = new int[2];
      Integer activeUserPeak = second2Cnt.values().stream().max(Comparator.comparingInt(i -> i)).orElse(0);
      ans[0] = activeUserPeak;

      int maxCnt = 0;
      List<Integer> activeUserPeakSeconds = second2Cnt.entrySet().stream().filter(entry -> entry.getValue().equals(activeUserPeak)).map(Map.Entry::getKey).collect(Collectors.toList());

      // O(n)
      for (int i = 0; i < activeUserPeakSeconds.size(); ) {
      int j = i;
      int groupSeconds = 1;
      for (; j < activeUserPeakSeconds.size(); j++) {
            if (continuous(activeUserPeakSeconds.get(i), activeUserPeakSeconds.get(i + 1))) {
                  groupSeconds++;
            } else {
                  break;
            }
      }
      maxCnt = Math.max(maxCnt, groupSeconds);
      i = j;
      }
      ans[1] = maxCnt;
      return ans;
}

复杂度

时间

收集每秒对应在线人数时存在循环套循环，复杂度O(n^2)。

空间

额外使用了LinkedHashMap有序记录时间、在线人数信息，空间复杂度O(n)。

等式+map

循环套循环，一般可以用map优化。

同时这里隐含一个等式关系：

1

当前时刻在线人数 = 上一秒在线人数 - 当前秒下线人数 + 当前秒上线人数

因此，我们先用一轮循环统计：当前秒上线人数、当前秒下线人数。再用一次循环计算当前时刻在线人数。

代码

 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

public int[] calculateActiveUserPeakAndLastingTime(Log[] logs) {
      // 上线时刻-》人数
      Map<Integer, Integer> loginTime2Cnt = new LinkedHashMap<>();
      // 下线时刻-》人数
      Map<Integer, Integer> logoutTime2Cnt = new LinkedHashMap<>();
      // O(n)
      for (Log log : logs) {
            int loginTime = log.loginTime;
            loginTime2Cnt.put(loginTime, loginTime2Cnt.getOrDefault(loginTime, 0) + 1);
            int logoutTime = log.logoutTime;
            logoutTime2Cnt.put(logoutTime, logoutTime2Cnt.getOrDefault(logoutTime, 0) + 1);
      }
      // 所有时刻
      Set<Integer> secondSet = loginTime2Cnt.keySet();
      secondSet.addAll(logoutTime2Cnt.keySet());

      // O(n)
      // 当前时刻在线人数 = 上一秒在线人数 - 当前秒下线人数 + 当前秒上线人数
      Map<Integer, Integer> second2Cnt = new LinkedHashMap<>();
      for (Integer second : secondSet) {
            Integer loginCnt = loginTime2Cnt.getOrDefault(second, 0);
            Integer logoutCnt = logoutTime2Cnt.getOrDefault(second, 0);
            second2Cnt.put(second, second2Cnt.getOrDefault(second - 1, 0) - logoutCnt + loginCnt);
      }
      int[] ans = new int[2];
      Integer activeUserPeak = second2Cnt.values().stream().max(Comparator.comparingInt(i -> i)).orElse(0);
      ans[0] = activeUserPeak;

      int maxCnt = 0;
      List<Integer> activeUserPeakSeconds = second2Cnt.entrySet().stream().filter(entry -> entry.getValue().equals(activeUserPeak)).map(Map.Entry::getKey).collect(Collectors.toList());

      // O(n)
      for (int i = 0; i < activeUserPeakSeconds.size(); ) {
      int j = i;
      int groupSeconds = 1;
      for (; j < activeUserPeakSeconds.size(); j++) {
            if (continuous(activeUserPeakSeconds.get(i), activeUserPeakSeconds.get(i + 1))) {
                  groupSeconds++;
            } else {
                  break;
            }
      }
      maxCnt = Math.max(maxCnt, groupSeconds);
      i = j;
      }
      ans[1] = maxCnt;
      return ans;
}

复杂度

时间

通过两轮循环+map的方式优化了粗暴解，复杂度O(n)。

空间

额外使用了Map统计了上下线人数、在线人数、时间秒数，空间复杂度O(n)。