0390. Elimination Game¶
题目信息¶
- 题号:
0390
- 难度:
Medium
- 主题:
整数序列、交替方向、隔项删除、最终剩余值
- 原题:
- 重点:
第一轮从左开始、每轮先删除当前方向的第一个元素并隔一个删除、方向持续交替
题目重述¶
从按升序排列的整数序列 [1, 2, ..., n] 开始。第一轮从左向右,删除最左侧元素以及此后每隔一个元素;第二轮对剩余序列从右向左,删除最右侧元素以及此后每隔一个元素。之后不断交替方向并重复相同规则,直到序列只剩一个整数。
返回最后留下的整数。n 位于 [1, 10^9]。每一轮删除操作都基于上一轮保留下来的顺序;从右向左的一轮也必须先删除当时最右侧的元素。
自建示例¶
偶数个初始元素:
输入:n = 6
输出:4
解释:[1,2,3,4,5,6] 从左删除后剩 [2,4,6];再从右删除 6 和 2,最后只剩 4。
只有一个元素:
输入:n = 1
输出:1
解释:序列已经只含一个整数,不需要执行删除。
只跟踪当前序列的首项、步长和长度¶
每轮删除后,剩余序列仍是等差序列。设当前最小值为 head,相邻元素间距为 step,剩余个数为 remaining。从左向右删除时,首项必被删掉;从右向左删除时,只有剩余个数为奇数时首项才会被删掉。首项是否移动一格由此确定,轮后步长翻倍,长度减半,方向交替。
不需要实际保存序列,n 很大时也只执行对数轮次。
C++ 实现¶
class Solution {
public:
int lastRemaining(int n) {
long long head = 1;
long long step = 1;
long long remaining = n;
bool fromLeft = true;
while (remaining > 1) {
if (fromLeft || (remaining % 2 == 1)) {
head += step;
}
remaining /= 2;
step *= 2;
fromLeft = !fromLeft;
}
return static_cast<int>(head);
}
};
代码分析¶
head 只在本轮最左元素被删除时前进,step 记录压缩后相邻保留元素的间隔;这些量足以恢复下一轮的等差序列。每轮长度至少减半,时间复杂度为 O(log n),额外空间为 O(1)。