Question

1285. 找到连续区间的开始和结束数字

English Version

题目描述

表：Logs

+---------------+---------+
| Column Name   | Type  |
+---------------+---------+
| log_id    | int   |
+---------------+---------+
id 是上表具有唯一值的列。
上表的每一行包含日志表中的一个 ID。

 

编写解决方案，得到 Logs 表中的连续区间的开始数字和结束数字。

返回结果表按照 start_id 排序。

结果格式如下面的例子。

 

示例 1：

输入：
Logs 表：
+------------+
| log_id   |
+------------+
| 1      |
| 2      |
| 3      |
| 7      |
| 8      |
| 10     |
+------------+
输出：
+------------+--------------+
| start_id   | end_id     |
+------------+--------------+
| 1      | 3      |
| 7      | 8      |
| 10     | 10       |
+------------+--------------+
解释：
结果表应包含 Logs 表中的所有区间。
从 1 到 3 在表中。
从 4 到 6 不在表中。
从 7 到 8 在表中。
9 不在表中。
10 在表中。

解法

方法一：分组 + 窗口函数

我们需要想办法将一段连续的日志分到同一组，然后对每一组进行聚合操作，得到每一组的开始日志和结束日志。

分组可以用以下两种方法实现：

1. 通过计算每个日志与前一个日志的差值，如果差值为 $1$，则说明这两个日志是连续的，我们设置 $delta$ 为 $0$，否则设置为 $1$。然后我们对 $delta$ 求前缀和，得到的结果就是每一行的分组的标识符。
2. 通过计算当前行的日志减去当前行的行号，得到的结果就是每一行的分组的标识符。

# Write your MySQL query statement below
WITH
  T AS (
    SELECT
      log_id,
      SUM(delta) OVER (ORDER BY log_id) AS pid
    FROM
      (
        SELECT
          log_id,
          IF((log_id - LAG(log_id) OVER (ORDER BY log_id)) = 1, 0, 1) AS delta
        FROM Logs
      ) AS t
  )
SELECT MIN(log_id) AS start_id, MAX(log_id) AS end_id
FROM T
GROUP BY pid;

方法二

# Write your MySQL query statement below
WITH
  T AS (
    SELECT
      log_id,
      log_id - ROW_NUMBER() OVER (ORDER BY log_id) AS pid
    FROM Logs
  )
SELECT MIN(log_id) AS start_id, MAX(log_id) AS end_id
FROM T
GROUP BY pid;