0390. 消除游戏【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学递推

1. 📝 题目描述

• leetcode

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

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

给你整数 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

2. 🎯 s.1 - 数学递推

c

int lastRemaining(int n) {
    int head = 1, step = 1, remaining = n;
    bool left = true;
    while (remaining > 1) {
        if (left || remaining % 2 == 1) head += step;
        step *= 2;
        remaining /= 2;
        left = !left;
    }
    return head;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var lastRemaining = function (n) {
  let head = 1,
    step = 1,
    left = true,
    remaining = n
  while (remaining > 1) {
    if (left || remaining % 2 === 1) head += step
    step *= 2
    remaining = Math.floor(remaining / 2)
    left = !left
  }
  return head
}

py

class Solution:
    def lastRemaining(self, n: int) -> int:
        head, step, remaining, left = 1, 1, n, True
        while remaining > 1:
            if left or remaining % 2 == 1:
                head += step
            step *= 2
            remaining //= 2
            left = not left
        return head

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$

算法思路：

• 跟踪剩余序列的首元素 head，步长 step，方向 left
• 从左开始或剩余为奇数时，head 移动一步
• 每轮后步长翻倍、数量减半、方向反转