390. 消除游戏

🟠   🔖  递归 数学  🔗 力扣 LeetCode

题目

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer n, return the last number that remains in arr.

Example 1:

Input: n = 9

Output: 6

Explanation:

arr = [1 , 2, 3 , 4, 5 , 6, 7 , 8, 9]

arr = [2, 4 , 6, 8]

arr = [2 , 6]

arr = [6]

Example 2:

Input: n = 1

Output: 1

Constraints:

• 1 <= n <= 10^9

题目大意

列表 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

解题思路

1. 观察删除规律

每轮的删除分为两种方式：

• 从左到右删除：序列中每个奇数位置的元素都会被删除。这时，剩余的元素序列首项始终发生变化。
• 从右到左删除：若剩余元素数量为奇数时，序列首项也会变化；若为偶数时，序列首项保持不变。

2. 关键变量

• head：记录当前序列的起始数字。
• step：当前序列中两个相邻数字之间的距离，初始为 1。
• n：当前序列中剩余的数字个数。
• left：布尔变量，标识当前轮的删除方向，true 表示从左到右，false 表示从右到左。

3. 状态更新规则

• 更新首项 (head)
  • 如果从左到右删除，首项一定变化：head += step
  • 如果从右到左删除，只有当 n 为奇数时首项变化：head += step
• 更新步长 (step)
  • 每轮步长加倍：step *= 2
• 更新剩余长度 (n)
  • 每轮删除一半元素：n = Math.floor(n / 2)
• 切换方向
  • left = !left

4. 算法结束条件

当序列只剩下一个元素时 (n === 1)，即为最终结果。

复杂度分析

• 时间复杂度：O(log n)，每轮 n 减半，因此需要进行 log n 轮操作。
• 空间复杂度：O(1)，只使用了常数空间存储变量。

代码

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

相关题目

题号	标题	题解	标签	难度	力扣
2293	极大极小游戏	[✓]	数组 模拟	🟢	🀄️ 🔗