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