暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

单挑力扣(LeetCode)SQL题:1285. 找到连续区间的开始和结束数字(难度:中等)

跟强哥学SQL 2022-09-01
262

给题目: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 表中的所有区间。
    13 在表中。
    46 不在表中。
    78 在表中。
    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;

        精选必读

        1、单挑力扣(LeetCode)SQL题:1303. 求团队人数

        2、单挑力扣(LeetCode)SQL题:1308. 不同性别每日分数总计

        3、单挑力扣(LeetCode)SQL题:1077. 项目员工 III(难度:中等)

        4、我敢打赌,没几个人知道NULL值的真正含义!

        文章转载自跟强哥学SQL,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

        评论