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

(通过次数8,111 | 提交次数9,900,通过率81.93%)

表:Logs
+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| log_id        | int     |
+---------------+---------+
log_id 是上表的主键。
上表的每一行包含日志表中的一个 log_id

后来一些 ID 从Logs表中删除。编写一个 SQL 查询得到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 在表中。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-the-start-and-end-number-of-continuous-ranges

#测试数据
Create table If Not Exists Logs (log_id int);

insert into Logs (log_id) values ('1');
insert into Logs (log_id) values ('2');
insert into Logs (log_id) values ('3');
insert into Logs (log_id) values ('7');
insert into Logs (log_id) values ('8');
insert into Logs (log_id) values ('10');

解题思路:

从题目描述和高达81.93%的通过率上来看,似乎这道题很简单,其实不然。

这是一道典型的SQL算法题:求连续区间。

算法这东西,说起来很玄乎,实际上就是针对一个或一类问题的计算方法(解决方案)。

而算法能力,又与数学能力挂勾。

关于数学,网上有一句流行说法:友谊会走散,爱情会变淡,困难会让你痛苦,生活会使你屈服……只有数学不会,不会就是不会。

所以,这道题,对于会的小伙伴,很简单;对于不会的小伙伴,很难!甚至难到怀疑人生:这样的结果也可以使用SQL语句计算出来?

不用怀疑,SQL当然可以完成!下面进入正题。

对于求连续区间,有几种常见的方法,都是基于连续区间的特性来进行计算的。

第一种特性:一个有序的集市,错位相减,可以得到区间的开始值和结束值;

第二种特性:如果一个数字是一个区间的开始值,那么这个数字-1一定不在集合中;相应的,如果一个数字是一个区间的结束值,那么这个数字+1一定不在集合中;

第三种特性:一个有序的集合,如果某几个值是连续的,那么这几个值-它的序号一定是相同的;

上面几个特性理解起来比较抽象,这里我就不一一展开解释了。对于求连续区间的问题,过几天我会专门出一篇推文进行详细的解说。

下面的参考答案,是基于第三种特性给出的,是SQL写起来最简洁的一种。

参考SQL:


select 
    min(a.log_id) start_id,
    max(a.log_id) end_id
from
(
    select
        a.log_id,
        a.log_id - row_number() over(order by a.log_id) rn
    from Logs a
)a
group by a.rn;
12-28 18:00