给题目: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;