leetcode-Consecutive numbers

Write a SQL query to find all numbers that appear at least three times consecutively.

+----+-----+
| Id | Num |
+----+-----+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 1 |
| 6 | 2 |
| 7 | 2 |
+----+-----+

For example, given the above Logs table, 1 is the only number that appears consecutively for at least three times.


思路:

自己没看题解做出来的第一道middle难度的题目,这个题和Rasing Temprature很像,考察的都是一个表中不同元组之间的某些属性的比较

那个easy的题目只要比较连续的两行就好,而这个题目要比较三行

将easy题目的两种解法套用过来,其中一个会超时,及O(2n^2)时间复杂度的那个嵌套选择算法,我分析这种算法之所以超时是因为每一次子select都要遍历整张表来判断where a.Id = c.Id - 2和where a.Id = b.Id-1,而当表的数据非常大的时候,速度就会很慢

第二种AC了的算法,感觉是一种消耗空间节省时间的方法,我们建立了表格之后,只需要遍历一遍就可以得出最后的答案。


AC代码:
select distinct a.Num as consecutiveNums
from Logs as a,Logs as b,Logs as c
where a.Id = b.Id - 1 and a.Id = c.Id - 2 and a.Num = b.Num and a.Num = c.Num
TLE代码:
select distinct a.Num as ConsecutiveNums
from Logs as a
where a.Num = (
select b.Num
from Logs as b
where a.Id = b.Id -1
)
and
a.Num = (
select c.Num
from Logs as c
where a.Id = c.Id -2
)
上一篇:Day11 空时编码理论之正交空时分组码和垂直分层空时编码


下一篇:转载:js和as间的交互