1613. 找到遗失的ID（难度：中等）

题目描述

（通过次数4,042 | 提交次数5,478，通过率73.79%）

表: Customers
+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| customer_id   | int     |
| customer_name | varchar |
+---------------+---------+
customer_id 是该表主键.
该表第一行包含了顾客的名字和id.

写一个 SQL 语句,找到所有遗失的顾客id.遗失的顾客id是指那些不在Customers表中,值却处于1和表中最大customer_id之间的id.
注意:最大的customer_id值不会超过100.
返回结果按ids 升序排列
查询结果格式如下例所示。

示例 1:
输入：
Customers 表:
+-------------+---------------+
| customer_id | customer_name |
+-------------+---------------+
| 1           | Alice         |
| 4           | Bob           |
| 5           | Charlie       |
+-------------+---------------+
输出：
+-----+
| ids |
+-----+
| 2   |
| 3   |
+-----+
解释：
表中最大的customer_id是5, 所以在范围[1,5]内, ID2和3从表中遗失.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-missing-ids

//测试数据
Create table If Not Exists Customers (customer_id int, customer_name varchar(20));

insert into Customers (customer_id, customer_name) values ('1', 'Alice');
insert into Customers (customer_id, customer_name) values ('4', 'Bob');
insert into Customers (customer_id, customer_name) values ('5', 'Charlie');

解题思路

题目本身很容易理解，需求也不难：找到1至最大customer_id之间的缺失值。

根据分步法，解答这个题目，可能需要如下两个步骤：

**第一步**：构建出一个1到最大customer_id之间的所有值的集合；

**第二步**：从集合中，剔除Customers表中已存在的customer_id；

第二步比较简单。难点在第一步：构建一个customer_id的全集。

SQL语言比较擅长处理集合中存在的元素。比如过滤、分组、统计、关联等。

但对处理集合中本身不存在的元素并不擅长。

为此，我专门翻了一遍《SQL必知必会（第4版）》（关注公众号xuesql，回复关键字“SQL必知必会”，获取电子版免费下载链接），发现里面并未提及对不存在元素如何生成。

而我们在MySQL、Oracle等数据库中常用的方法，都是这些数据库本身的方言。所以语法上会有些差别，甚至有些写法，还是某些数据库独有的。

下面主要针对MySQL和Oracle这两个数据库，介绍一下在构建一个集合时的写法：

**MySQL数据库**：主要使用递归实现

#方法一
with recursive tmp as (
    select 1 as customer_id 
     union all 
    select customer_id+1 from tmp where customer_id < (select max(customer_id) from Customers)
)
select * from tmp;
#方法二
with recursive tmp(n) as (
    select 1 as customer_id
    union all
    select n+1 from tmp where n<(select max(customer_id) from Customers)
)
select * from tmp;

**Oracle数据库**：主要使用递归和connect by关键字实现

#方法一
with tmp(customer_id) as (
    select 1 as customer_id from dual
    union all
    select customer_id + 1 from tmp where customer_id < (select max(customer_id) from customers)
)
select * from tmp;
#方法二
select rownum as customer_id 
from dual 
connect by rownum <= (select max(customer_id) from customers);

参考SQL

未特别说明的情况下，参考SQL为基于MySQL8.0实现。

with recursive tmp as (
    select 1 as customer_id 
     union all 
    select customer_id+1 from tmp where customer_id < (select max(customer_id) from Customers)
)
select 
    customer_id as ids
from tmp
where customer_id not in (select customer_id from Customers);