LeetCode 390 消除游戏 Swift 算法解析

给你整数 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 解决方案：

class Solution {
    func lastRemaining(_ n: Int) -> Int {
        if n == 1 {
            return 1
        }
        // head: 当前剩余序列的第一个元素
        var head = 1
        // step: 相邻剩余元素之间的差值（等差数列的公差）
        var step = 1
        // count: 剩余元素的数量
        var count = n
        // leftToRight: 本轮是否从左到右消除
        var leftToRight = true
        while count > 1 {
            if leftToRight {
                // 从左到右：总是会删除第一个元素，所以 head 要后移
                head += step
            } else {
                // 从右到左：只有当剩余数量为奇数时，才会删到第一个元素
                if count % 2 == 1 {
                    head += step
                }
            }
            step *= 2
            count /= 2
            leftToRight.toggle()
        }
        return head
    }
}

题解代码分析

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

核心观察：等差数列

每一轮消除后，剩余数字都形成一个等差数列。例如 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：

if leftToRight { 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 {
    if count % 2 == 1 {
        head += step
    }
}

step 和 count 的更新

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

step *= 2
count /= 2
leftToRight.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)
• 逻辑简洁，易于实现