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)``。