390. 消除游戏

390. 消除游戏 390. 消除游戏

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 109

解题思路：
从题目中可以分析，我们可以使用一个变量来维护数组最左边的值，每次循环删除时都会将数组减半，当数组长度为1时，返回此变量及为此题答案，那什么时候维护此时变量呢？
查看算法可得出更新变量应该存在四种情况：

• 当数组长度为奇数时，且从左向右删除数字，此时最左边的数字需要删除，此时我们需要将左边变量往右进行偏移。
• 当数组长度为偶数时，且从左向右删除数字，此时最左边的数字需要删除，此时我们需要将左边变量往右进行偏移。
• 当数组长度为奇数时，且从右向左删除数字，此时最左边的数字需要删除，此时我们需要将左边变量往右进行偏移。
• 当数组长度为偶数时，且从右向左删除数字，此时最左边的数字不需要删除，此时我们不需要将左边变量往右进行偏移。

举例：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

1. 当此时数组为1, 2, 3, 4, 5, 6, 7, 8, 9时，我们可设置初始变量num = 1，count = n， time = 0， step = 1。
2. 这是第一次从左往右删除数字，此时数组长度为奇数，需要将最左边的数往右偏移step，此时需要将 num = num + step，此时num = 2，需要将step *= 2，此时左移一位，step = step << 1,step = 2,将数组长度count右移一位，count = count >> 1,count = 4，可得最终数组2，4，6，8。
3. 第二次需要从右向左删除数字，此时数组长度为偶数，不需要将最左边的数往右偏移step，此时需要将 num = num，此时num = 2，需要将step *= 2，此时左移一位，step = step << 1,step = 4，将数组长度count右移一位，count = count >> 1,count = 2，可得最终数组2，6。
4. 第三次需要从左向右删除数字，此时数组长度为偶数，需要将最左边的数往右偏移step，此时需要将 num = num + step，此时num = 6，需要将step *= 2，此时左移一位，step = step << 1,step = 8，将数组长度count右移一位，count = count >> 1,count = 1，跳出循环，可得最终数组6。

代码：

int lastRemaining(int n){
    if(n == 1)
        return 1;
    int count = n;
    int time = 0;
    int num = 1;
    int step = 1;
    while(count > 1)
    {
        if(time % 2 == 0)
        {
            num = num + step;
        }
        else
        {
            num = (count % 2 == 0) ? num : num + step;
        }
        time++;
        step = step << 1;
        count = count >> 1;        
    }
    return num;
}

时间复杂度： O(logn)
空间复杂度： O(1)

新年第二天，大家一起加油。