LeetCode题练习与总结：游戏玩法分析 Ⅳ -- 550

标签：登录 -- 复杂度 550 玩家 Activity id 查询 LeetCode

一、题目描述

SQL Schema > Pandas Schema >

Table: Activity

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| player_id    | int     |
| device_id    | int     |
| event_date   | date    |
| games_played | int     |
+--------------+---------+
（player_id，event_date）是此表的主键（具有唯一值的列的组合）。
这张表显示了某些游戏的玩家的活动情况。
每一行是一个玩家的记录，他在某一天使用某个设备注销之前登录并玩了很多游戏（可能是 0）。

编写解决方案，报告在首次登录的第二天再次登录的玩家的比率，四舍五入到小数点后两位。换句话说，你需要计算从首次登录日期开始至少连续两天登录的玩家的数量，然后除以玩家总数。

结果格式如下所示：

示例 1：

输入：
Activity table:
+-----------+-----------+------------+--------------+
| player_id | device_id | event_date | games_played |
+-----------+-----------+------------+--------------+
| 1         | 2         | 2016-03-01 | 5            |
| 1         | 2         | 2016-03-02 | 6            |
| 2         | 3         | 2017-06-25 | 1            |
| 3         | 1         | 2016-03-02 | 0            |
| 3         | 4         | 2018-07-03 | 5            |
+-----------+-----------+------------+--------------+
输出：
+-----------+
| fraction  |
+-----------+
| 0.33      |
+-----------+
解释：
只有 ID 为 1 的玩家在第一天登录后才重新登录，所以答案是 1/3 = 0.33

二、解题思路

为了解决这个问题，我们需要执行以下步骤：

找出每个玩家的首次登录日期。
对于每个玩家，检查他们在首次登录后的第二天是否再次登录。
计算至少连续两天登录的玩家数量。
计算玩家总数。
计算比率并四舍五入到小数点后两位。

三、具体代码

-- 1. 找出每个玩家的首次登录日期
WITH FirstLogin AS (
    SELECT player_id, MIN(event_date) AS first_login_date
    FROM Activity
    GROUP BY player_id
)

-- 2. 检查每个玩家在首次登录后的第二天是否再次登录
, SecondDayLogin AS (
    SELECT f.player_id
    FROM FirstLogin f
    JOIN Activity a ON f.player_id = a.player_id
    WHERE a.event_date = DATE_ADD(f.first_login_date, INTERVAL 1 DAY)
)

-- 3. 计算至少连续两天登录的玩家数量
, ContinuousLoginCount AS (
    SELECT COUNT(DISTINCT player_id) AS continuous_login_count
    FROM SecondDayLogin
)

-- 4. 计算玩家总数
, TotalPlayers AS (
    SELECT COUNT(DISTINCT player_id) AS total_players
    FROM Activity
)

-- 5. 计算比率并四舍五入到小数点后两位
SELECT ROUND(
    (SELECT continuous_login_count FROM ContinuousLoginCount) /
    (SELECT total_players FROM TotalPlayers),
    2
) AS fraction;

这个查询首先通过FirstLogin子查询找到每个玩家的首次登录日期。然后，SecondDayLogin子查询检查这些玩家是否在首次登录后的第二天再次登录。ContinuousLoginCount子查询计算至少连续两天登录的玩家数量，而TotalPlayers子查询计算所有不同的玩家数量。最后，我们计算比率并使用ROUND函数四舍五入到小数点后两位。

四、时间复杂度和空间复杂度

时间复杂度和空间复杂度是用于评估算法性能的两个重要指标。在数据库查询中，这些概念可以用来评估查询的效率和资源消耗。以下是对给定SQL查询的时间复杂度和空间复杂度的分析：

1. 时间复杂度

找出每个玩家的首次登录日期（FirstLogin）：
- 这个步骤需要对Activity表进行全表扫描，以确定每个玩家的最小event_date。
- 时间复杂度：O(n)，其中n是Activity表中的行数。
检查每个玩家在首次登录后的第二天是否再次登录（SecondDayLogin）：
- 这个步骤需要将FirstLogin子查询的结果与Activity表进行连接操作。
- 对于每个玩家的首次登录日期，需要检查Activity表中是否存在第二天的登录记录。
- 时间复杂度：O(m * n)，其中m是首次登录的玩家数量，n是Activity表中的行数。在最坏的情况下，每个玩家都需要与Activity表中的每一行进行比较。
计算至少连续两天登录的玩家数量（ContinuousLoginCount）：
- 这个步骤是对SecondDayLogin子查询的结果进行计数。
- 时间复杂度：O(m)，其中m是至少连续两天登录的玩家数量。
计算玩家总数（TotalPlayers）：
- 这个步骤是对Activity表中的player_id进行去重计数。
- 时间复杂度：O(n)，其中n是Activity表中的行数。
计算比率并四舍五入到小数点后两位：
- 这个步骤是计算两个计数值的比率，并进行四舍五入。
- 时间复杂度：O(1)，这是一个常数时间的操作。

总的时间复杂度是所有步骤中时间复杂度最高的那个，即O(m * n)。

2. 空间复杂度

FirstLogin、SecondDayLogin、ContinuousLoginCount、TotalPlayers子查询都需要存储中间结果。
- 空间复杂度取决于每个子查询的结果集大小。
- 假设每个子查询的结果集大小大致等于Activity表的大小，则空间复杂度为O(n)。
最终的比率计算只需要存储两个数字（连续登录的玩家数量和总玩家数量），因此空间复杂度为O(1)。

总的空间复杂度是所有步骤中空间复杂度最高的那个，即O(n)。

注意：在实际数据库操作中，数据库优化器可能会对查询进行优化，这可能会改变实际的时间复杂度。此外，由于数据库内部操作和索引的使用，实际性能可能会与理论分析有所不同。

五、总结知识点

公用表表达式 (Common Table Expressions, CTEs):
- 使用 WITH 关键字定义了多个公用表表达式（CTEs），这些表达式允许我们将查询分解为多个步骤，每个步骤都可以引用前一个步骤的结果。
聚合函数 (Aggregate Functions):
- 使用了 MIN 函数来找出每个玩家的首次登录日期。
- 使用了 COUNT 和 DISTINCT 来计算唯一的玩家数量。
分组 (GROUP BY Clause):
- 使用 GROUP BY 子句对玩家的 player_id 进行分组，以便为每个玩家计算最小登录日期。
连接 (JOINs):
- 使用了 JOIN 操作来将 FirstLogin CTE 与 Activity 表连接起来，以便检查玩家在首次登录后的第二天是否再次登录。
日期函数 (Date Functions):
- 使用了 DATE_ADD 函数来计算首次登录日期后的第二天。
子查询 (Subqueries):
- 在 SecondDayLogin 和 ContinuousLoginCount CTEs 中使用了子查询来过滤和计算所需的数据。
- 在最终的选择语句中，使用了子查询来获取连续登录的玩家数量和总玩家数量。
四舍五入函数 (ROUND Function):
- 使用了 ROUND 函数来将计算出的比率四舍五入到小数点后两位。
数据类型转换和计算 (Arithmetic Operations):
- 在最终的选择语句中，执行了除法运算来计算比率，并且隐式地将结果转换为可以进行除法运算的数据类型。
SQL 语法结构:
- 代码展示了如何构建一个多步骤的SQL查询，包括定义CTEs、执行聚合操作、使用连接和子查询，以及最终的计算和格式化输出。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：登录,--,复杂度,550,玩家,Activity,id,查询,LeetCode
From： https://blog.csdn.net/weixin_62860386/article/details/145149997