Skip to content

Latest commit

 

History

History
141 lines (107 loc) · 3.28 KB

README.md

File metadata and controls

141 lines (107 loc) · 3.28 KB
Raw
comments difficulty edit_url tags
true
中等
数据库

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. 通过计算当前行的日志减去当前行的行号，得到的结果就是每一行的分组的标识符。

MySQL

# 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;

方法二

MySQL

# 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;