LeetCode 390 消除游戏 - Swift 题解

摘要

这道题其实挺有意思的，它要求我们模拟一个交替从左到右、从右到左的消除过程，最后找出剩下唯一一个数字。听起来像是约瑟夫问题的变种，但实际上可以通过数学规律来高效解决。

由于 n 最大可以到 10^9，如果直接模拟整个消除过程，时间和空间都会爆炸。我们需要找出其中的规律：每一轮消除后，剩余数字形成一个等差数列，我们只需要维护"头元素"和"步长"，就能推算出下一轮的状态，而不需要真正维护整个数组。今天我们就用 Swift 来搞定这道题，顺便聊聊这种数学建模的思路在实际开发中的应用。

描述

题目要求是这样的：列表arr由在范围[1, n]中的所有整数组成，并按严格递增排序。请你对arr应用下述算法：

1. 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾
2. 重复上面的步骤，但这次是从右到左，删除最右侧的数字，然后剩下的数字每隔一个删除一个
3. 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字

给你整数n，返回arr最后剩下的数字。

示例 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 <= n <= 10^9

这道题的核心思路是：每一轮消除后，剩余数字构成一个等差数列。我们只需维护当前等差数列的"头元素"和"步长"，以及剩余数量，就能用 O(log n) 的时间推算出最终答案，而不需要真正模拟整个数组。

题解答案

下面是完整的 Swift 解决方案：

classSolution{funclastRemaining(_n:Int)->Int{ifn==1{return1}// head: 当前剩余序列的第一个元素varhead=1// step: 相邻剩余元素之间的差值（等差数列的公差）varstep=1// count: 剩余元素的数量varcount=n// leftToRight: 本轮是否从左到右消除varleftToRight=truewhilecount>1{ifleftToRight{// 从左到右：总是会删除第一个元素，所以 head 要后移head+=step}else{// 从右到左：只有当剩余数量为奇数时，才会删到第一个元素ifcount%2==1{head+=step}}step*=2count/=2leftToRight.toggle()}returnhead}}

题解代码分析

让我们一步步分析这个解决方案。

核心观察：等差数列

每一轮消除后，剩余数字都形成一个等差数列。例如 n=9 时：

• 初始：[1, 2, 3, 4, 5, 6, 7, 8, 9]，头=1，步长=1，数量=9
• 从左到右后：[2, 4, 6, 8]，头=2，步长=2，数量=4
• 从右到左后：[2, 6]，头=2，步长=4，数量=2
• 从左到右后：[6]，头=6，步长=8，数量=1

我们只需要维护head（头元素）、step（步长）、count（剩余数量），就能完整描述当前状态，无需保存整个数组。

从左到右消除时 head 的更新

从左到右消除时，我们总是先删掉第一个元素，然后每隔一个删一个。因此，无论剩余数量是奇数还是偶数，原来的第一个元素都会被删掉，新的第一个元素就是原来的第二个元素。

由于剩余序列是等差数列，相邻元素相差step，所以新的 head 为head + step：

ifleftToRight{head+=step}

从右到左消除时 head 的更新

从右到左消除时，我们先删最右边，再每隔一个删。这时头元素是否被删，取决于剩余数量的奇偶性。

• 若count为偶数：例如[2, 4, 6, 8]，从右删 8、4，剩下[2, 6]，头 2 保留，head 不变
• 若count为奇数：例如[2, 4, 6]，从右删 6、2，剩下[4]，头 2 被删，新的头是 4，head 需要加上 step

所以：

if!leftToRight{ifcount%2==1{head+=step}}

step 和 count 的更新

每轮消除后，相邻剩余元素之间的间隔会翻倍，因此step *= 2。剩余数量大约减半，所以count /= 2：

step*=2count/=2leftToRight.toggle()

边界情况

当n == 1时，直接返回 1，无需进入循环。

完整执行流程示例（n=9）

1. head=1, step=1, count=9, leftToRight=true
   从左到右：head=2, step=2, count=4, leftToRight=false

2. head=2, step=2, count=4, leftToRight=false
   count 为偶数，head 不变：head=2, step=4, count=2, leftToRight=true

3. head=2, step=4, count=2, leftToRight=true
   从左到右：head=6, step=8, count=1, leftToRight=false

4. count=1，退出循环，返回 6

示例测试及结果

示例 1：n = 9

执行过程：

1. 初始：head=1, step=1, count=9
2. 从左到右：head=2, step=2, count=4
3. 从右到左（count 偶数）：head=2, step=4, count=2
4. 从左到右：head=6, step=8, count=1
5. 返回 6

结果：6

示例 2：n = 1

执行过程：

• 直接返回 1，不进入循环

结果：1

示例 3：n = 6

模拟过程：

• 初始：[1,2,3,4,5,6]
• 从左到右：[2,4,6]
• 从右到左：[4]
• 返回 4

算法过程：

1. head=1, step=1, count=6，从左到右：head=2, step=2, count=3
2. count 为奇数，从右到左会删到头：head=4, step=4, count=1
3. 返回 4

示例 4：n = 2

模拟过程：

• 初始：[1,2]
• 从左到右：删除 1，剩下[2]
• 返回 2

算法过程：

1. head=1, step=1, count=2，从左到右：head=2, step=2, count=1
2. 返回 2

时间复杂度

时间复杂度：O(log n)

每一轮 count 约减半，因此循环次数约为 log₂(n)。对于 n = 10^9，大约 30 次循环即可结束。

空间复杂度

空间复杂度：O(1)

只使用了 head、step、count、leftToRight 等少量变量，与 n 无关。

实际应用场景

这种“用数学规律替代模拟”的思路在实际开发中很有用：

场景一：约瑟夫问题

经典的约瑟夫问题也是每隔 k 个人淘汰一人，最后剩下谁。同样可以不用模拟，而用递推或公式计算。

场景二：分批处理

当数据量巨大且处理规则有规律时（如每隔一批保留一批），可以像本题一样抽象成 head、step、count，避免真正构建和遍历整个序列。

场景三：游戏逻辑

某些回合制游戏每轮按固定规则淘汰角色，若规则呈现周期性或可归纳的数学规律，可以用类似方式在 O(log n) 时间内算出结果。

总结

本题的关键在于发现：每轮消除后剩余数字构成等差数列，只需维护头元素、步长和数量，就能在 O(log n) 时间和 O(1) 空间内得到最终结果。

要点总结：

1. 从左到右消除：head 一定增加 step
2. 从右到左消除：仅在 count 为奇数时 head 增加 step
3. 每轮 step 翻倍，count 减半

算法优势：

• 时间复杂度 O(log n)，适合 n 极大的情况
• 空间复杂度 O(1)
• 逻辑简洁，易于实现