---

0390. 消除游戏

• 标签：递归、数学
• 难度：中等

题目链接

• 0390. 消除游戏 - 力扣

题目大意

描述：

给定一个整数 $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：递归 + 数学规律

观察消除过程，我们可以发现以下规律：

1. 从左到右消除：每次消除后，剩余数字的间隔变为原来的 $2$ 倍，起始位置变为原来的第 $2$ 个位置。
2. 从右到左消除：每次消除后，剩余数字的间隔变为原来的 $2$ 倍，但起始位置需要重新计算。

设 $f(n)$ 表示从 $1$ 到 $n$ 的数字经过消除游戏后剩余的数字。

递推关系：

• 当 $n = 1$ 时：$f(1) = 1$。
• 当 $n > 1$ 时：
  • 从左到右消除后，剩余 $\lfloor \frac{n}{2} \rfloor$ 个数字，间隔为 $2$。
  • 然后从右到左消除，相当于对剩余数字进行镜像操作。
  • $f(n) = 2 \times (1 + \lfloor \frac{n}{2} \rfloor - f(\lfloor \frac{n}{2} \rfloor))$。

关键观察：

• 从左到右消除后，剩余数字为 $[2, 4, 6, 8, ...]$，共 $\lfloor \frac{n}{2} \rfloor$ 个。
• 这些数字可以重新编号为 $[1, 2, 3, 4, ...]$，共 $\lfloor \frac{n}{2} \rfloor$ 个。
• 对重新编号的数字进行消除游戏，得到 $f(\lfloor \frac{n}{2} \rfloor)$。
• 由于下一步是从右到左开始，需要计算镜像位置：$1 + \lfloor \frac{n}{2} \rfloor - f(\lfloor \frac{n}{2} \rfloor)$。
• 最后乘以 $2$ 得到在原序列中的位置。

示例验证（$n = 9$）：

1. 初始：$[1, 2, 3, 4, 5, 6, 7, 8, 9]$。
2. 从左到右消除：$[2, 4, 6, 8]$（剩余 $4$ 个数字）。
3. 重新编号：$[1, 2, 3, 4]$，对 $4$ 个数字进行消除游戏。
4. 计算 $f(4)$：$f(4) = 2 \times (1 + 2 - f(2)) = 2 \times (1 + 2 - 2) = 2$。
5. 镜像位置：$1 + 4 - 2 = 3$，对应原序列中的 $2 \times 3 = 6$。

思路 1：代码

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)

思路 1：复杂度分析

• 时间复杂度：$O(\log n)$，每次递归调用都将问题规模减半。
• 空间复杂度：$O(\log n)$，递归调用栈的深度为 $O(\log n)$。