0390. Elimination Game

题目信息

题号:

0390

难度:

Medium

主题:

整数序列、交替方向、隔项删除、最终剩余值

原题:

LeetCode 0390

重点:

第一轮从左开始、每轮先删除当前方向的第一个元素并隔一个删除、方向持续交替

题目重述

从按升序排列的整数序列 [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)。