教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文是「算法通关手册」LeetCode 题解库中第 390 题《消除游戏Elimination Game》的完整解析。这道题要求对区间[1, n]反复进行「从左到右、从右到左」交替删除的模拟过程但 $n$ 最大可达 $10^9$直接模拟必然超时。读完本文你将掌握如何从消除过程中抽取出「规模减半 镜像重编号」的数学规律用 $O(\log n)$ 的递归递推在常数级轮次内求出最后剩下的数字并理解它与约瑟夫环类问题如 LCR 187. 破冰游戏在思路上的差异。题目描述原题链接题目位于题解库 docs/solutions/0300-0399/elimination-game.md收录于 0300-0399 区间题解索引 与 题库总表。标签递归、数学难度中等。题目大意给定一个整数 $n$列表 $arr$ 由范围 $[1, n]$ 中的所有整数组成并按严格递增排序。请对 $arr$ 应用下述算法从左到右删除第一个数字然后每隔一个数字删除一个直到到达列表末尾重复上面的步骤但这次是从右到左。也就是删除最右侧的数字然后剩下的数字每隔一个删除一个不断重复这两步从左到右和从右到左交替进行直到只剩下一个数字。返回 $arr$ 最后剩下的数字。说明$1 \le n \le 10^{9}$。示例示例 1输入n 9 输出6 解释 arr [1, 2, 3, 4, 5, 6, 7, 8, 9] arr [2, 4, 6, 8] arr [2, 6] arr [6]示例 2输入n 1 输出1为什么不能直接模拟最直观的做法是使用循环链表或双端队列模拟整轮删除。但观察数据范围 $1 \le n \le 10^{9}$模拟需要维护 $n$ 个元素并执行 $n-1$ 次删除时间复杂度为 $O(n)$在 $n 10^9$ 时完全不可行即便不显式建表仅计算下标也要处理每轮近乎 $n/2$ 的扫描量同样无法通过。因此必须从消除过程的结构规律入手把「整表模拟」压缩成「规模减半的递归递推」这正是仓库 递归算法 章节所强调的递归三步法写递推公式 → 确定终止条件 → 翻译为代码的直接应用。思路递归 数学规律观察规律在消除过程中无论方向如何每一轮都会删掉约一半的元素剩余元素个数变为原来的 $\lfloor n/2 \rfloor$ 左右剩余元素之间的间隔变为原来的 2 倍序列的起点需要重新确定从左到右删时起点固定为第二个元素从右到左删时起点由剩余元素个数的奇偶性决定。于是问题从「$1 \sim n$ 的整段序列」缩小为「$1 \sim \lfloor n/2 \rfloor$ 的同类问题」只是下一次的起始方向发生了翻转而方向翻转正好可以通过「镜像对称」来刻画。递推公式推导设 $f(n)$ 表示从 $1$ 到 $n$ 的数字经过消除游戏后剩余的数字。终止条件当 $n 1$ 时$f(1) 1$。递推关系$n 1$第一轮从左到右消除后剩余 $\lfloor n/2 \rfloor$ 个数字它们为 $[2, 4, 6, 8, \dots]$间隔为 $2$把剩余数字除以 $2$ 重新编号为 $[1, 2, 3, 4, \dots]$共 $\lfloor n/2 \rfloor$ 个由于下一步是从右到左开始对重新编号后的序列做消除游戏等价于先求出「从左到右起手」的解 $f(\lfloor n/2 \rfloor)$再取它在序列中的镜像位置$1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor)$最后乘回间隔因子 $2$得到原序列中的位置。即核心递推式$$f(n) 2 \times \left(1 \left\lfloor \frac{n}{2} \right\rfloor - f\left(\left\lfloor \frac{n}{2} \right\rfloor\right)\right)$$关键点回顾从左到右消除后剩余数字为 $[2, 4, 6, 8, \dots]$共 $\lfloor n/2 \rfloor$ 个这些数字除以 $2$ 可重新编号为 $[1, 2, 3, 4, \dots]$对重新编号的数字进行消除游戏得到 $f(\lfloor n/2 \rfloor)$由于下一步从右到左开始需要计算镜像位置$1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor)$最后乘以 $2$ 得到在原序列中的位置。示例验证$n 9$初始$[1, 2, 3, 4, 5, 6, 7, 8, 9]$从左到右消除$[2, 4, 6, 8]$剩余 $4$ 个数字重新编号$[1, 2, 3, 4]$对 $4$ 个数字进行消除游戏计算 $f(4)$$f(4) 2 \times (1 2 - f(2)) 2 \times (1 2 - 2) 2$镜像位置$1 4 - 2 3$对应原序列中的 $2 \times 3 6$。结果与示例 1 的输出 $6$ 完全一致。参考代码class Solution: def lastRemaining(self, n: int) - int: def f(n): 计算从1到n的数字经过消除游戏后剩余的数字 if n 1: return 1 # 从左到右消除后剩余数字为[2,4,6,8,...]共n//2个 # 这些数字可以重新编号为[1,2,3,4,...] # 对重新编号的数字进行消除游戏得到f(n//2) # 由于下一步是从右到左需要计算镜像位置 return 2 * (1 n // 2 - f(n // 2)) return f(n)复杂度分析时间复杂度$O(\log n)$。每次递归调用都将问题规模减半递归深度为 $\log_2 n$空间复杂度$O(\log n)$。递归调用栈的深度为 $O(\log n)$。递推公式的原理拆解从左到右轮间隔翻倍与重编号第一轮「从左到右删除第一个然后隔一个删一个」之后保留下来的必然是所有偶数位元素 $[2, 4, 6, \dots]$。将其整体除以 $2$就等价于对 $[1, 2, 3, \dots, \lfloor n/2 \rfloor]$ 做一轮消除游戏——这正是问题规模减半的来源。整个过程的数学本质是「等比压缩 下标重映射」间隔因子从 $1$ 变为 $2$通过除以 $2$ 还原为以 $1$ 为起点的标准区间。从右到左轮镜像对称若下一步仍是从左到右那么答案就是 $2 \times f(\lfloor n/2 \rfloor)$。但本题第二步是从右到左起手等价于在重编号序列上「交换方向」。此时「方向」对结果的影响可用镜像位置刻画长度为 $m$ 的序列中位置 $i$ 的镜像位置为 $m 1 - i$。所以重编号序列上的解为 $f(m)$$m \lfloor n/2 \rfloor$考虑方向翻转后有效位置变为 $m 1 - f(m)$还原间隔因子得到 $2 \times (m 1 - f(m))$。这正是递推式 $f(n) 2 \times (1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor))$ 的由来。与递归三步法的对应对照仓库 docs/07_algorithm/07_02_recursive_algorithm.md 中给出的递归三步法写递推公式$f(n) 2 \times (1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor))$确定终止条件$n 1$ 时 $f(1) 1$即只剩一个数字时它自己就是答案翻译为代码递归函数主体只有一行 return终止条件由if n 1承担。递归执行时问题规模以 $\lfloor n/2 \rfloor$ 快速收敛最坏情况也只需 $\lfloor \log_2 n \rfloor 1$ 层因此在 $n \le 10^9$ 时递归深度约为 30 层远小于默认栈深度上限不存在栈溢出风险仓库文档也指出递归层数受栈空间限制深度不可控时应改写为迭代。扩展改写成迭代版本若不希望使用递归例如面试中被要求 $O(1)$ 辅助空间可以自底向上递推用变量维护「当前规模下的答案」与「当前规模」从 $2$ 一路推到 $n$。下面给出等价迭代实现class Solution: def lastRemaining(self, n: int) - int: # 维护当前区间长度 k 时「从左到右起手」的解 ans 1 # k 1 时答案 k 1 while k * 2 n: # 一次“左到右 右到左”合并推进 # 先做从左到右剩余元素个数 m k # 再做从右到左镜像位置 # 等价于对规模 k 的解做两次映射 m k ans 2 * (m 1 - ans) k m * 2 # 若剩余 k 后仍需从左到右再消一次根据 k 的奇偶决定起点 ...说明上述迭代骨架展示了「规模翻倍、方向交替」的推进方式实际提交时更简洁可靠的做法是直接采用递归版——因为每轮问题规模严格减半递归深度天然为 $O(\log n)$空间开销可以忽略。迭代写法需要额外维护「下一次起点」稍显繁琐但不改变时间复杂度 $O(\log n)$。关联与延伸与约瑟夫环类问题的对比仓库中还收录了结构相近的 LCR 187. 破冰游戏圆圈中最后剩下的数字标签同为递归、数学LCR 187 每次从当前起点数 $m$ 个删除一个最终答案通过 $f(n, m) [f(n-1, m) m] \bmod n$ 递推得到方向始终一致是典型的约瑟夫环问题本题每次删除一半元素且方向交替翻转递推关系变为 $f(n) 2 \times (1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor))$。两者共同点在于都拒绝模拟、都依赖「缩小问题规模 结果位置映射」的数学抽象差异点在于方向翻转引入了镜像对称项。把两道题放在一起对比可以更深刻地理解「规模减半类递归」的两大范式——同向位移约瑟夫环与镜像对称消除游戏。在本仓库中的检索线索本题题解收录于 docs/solutions/0300-0399/index.md在 题库总表 中可查到题目标签递归、数学与难度中等在 分类列表 的「递归算法题目」「数学题目」分类下可找到同类练习递归理论基础可参考 docs/07_algorithm/07_02_recursive_algorithm.md分治思想可参考 docs/07_algorithm/07_03_divide_and_conquer_algorithm.md。小结LeetCode 390「消除游戏」是「递归 数学」标签的典型中等题。它的核心价值在于训练两类能力问题压缩把 $n$ 个元素的交替删除压缩为 $\lfloor n/2 \rfloor$ 个元素的同构子问题坐标映射通过「除以间隔因子重编号」与「镜像位置 $m 1 - i$」把子问题的解还原回原序列。掌握了递推式 $f(n) 2 \times (1 \lfloor n/2 \rfloor - f(\lfloor n/2 \rfloor))$ 的推导过程就能以 $O(\log n)$ 的时间与空间在 $n 10^9$ 的数据范围下快速求解同时为理解约瑟夫环、快速幂、二分这类「规模减半」算法的思维模式打下基础。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 0004《寻找两个正序数组的中位数》基于二分查找的 O(log(mn)) 解法详解AlgoNote 算法通关手册LeetCode 0004《寻找两个正序数组的中位数》基于二分查找的 O log mn 解法详解AlgoNote 算法通关手册 导读 本篇技术指南围绕「教程文档知识库AlgoNote 算法通关手册递归算法Recursion从入门到实战——递推、回归与三步解题法AlgoNote 算法通关手册递归算法Recursion从入门到实战——递推、回归与三步解题法 本篇技术指南以 AlgoNote 仓库的 07_02_re教程文档知识库LeetCode 0112 路径总和Path Sum全解AlgoNote 算法通关手册中的递归 DFS 判定法LeetCode 0112 路径总和Path Sum全解AlgoNote 算法通关手册中的递归 DFS 判定法 本文依据 path sum.md http教程文档知识库上一篇从报错到跑通ESP32 固件下载失败的五类高频场景排查指南下一篇PS Vita 备份有救了免费开源 QCMA 三步搞定电脑与掌机内容管理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考