390 Elimination Game

题目

390 Elimination Game

题解

题目要求

从左向右对数组进行删除→保留→删除→保留的交替操作，到达右端后再从右向左进行同样的操作。重复上述操作，直到数组中只剩下一个元素为止。给定一个从1到n的连续数组序列，求最后剩下的元素。

分析

首先我们可以通过观察得知下列事实

• 由于是每隔一个元素进行删除，所以一轮删除之后会有一半的元素被删除，并且两个相邻元素之间的间隔会是原来的两倍

• 从左向右删除时，第二个元素一定会被保留；从右向左删除时，若此时元素的个数为奇数，那么第二个元素会被保留成为下一轮的第一个元素，否则被保留为下一轮第一个元素的将会是第一个元素

• 最后剩下的元素一定是上一轮中被保留下来的第一个（也是最后一个）元素

由上述事实，我们可以得出一个高效算出最后剩下的元素的算法：

1. 初始化间隔为1，元素个数为n

2. 在进行一轮删除时，通过间隔、元素个数和删除方向计算出下一轮的第一个元素。这个元素要么是当前这一轮的第一个元素，要么是当前轮的第二个元素，也就是第一个元素的值加上间隔值

3. 一轮删除结束后间隔翻倍，元素个数减半

4. 重复第2、3步直到元素个数变为1

复杂度

由于每一轮删除都会使得元素个数减半，所以总共有log(n)轮删除。每一轮删除都会遍历整个数组，所以总的时间复杂度为O(nlog(n))。因为只需要记录常数个变量，所以空间复杂度为O(1)。

代码

class Solution
{
public:
    int lastRemaining(int n)
    {
        bool left = true;
        int remain = n;
        int head = 1;
        int step = 1;

        while(remain != 1)
        {
            if (left || remain % 2 == 1)
            {
                head = head + step;
            }
            remain /= 2;
            step *= 2;
            left = !left;
        }

        return head;
    }
};