题目

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

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

示例：

输入：n = 9

输出：6

解释：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

arr = [2, 4, 6, 8]

arr = [2, 6]

arr = [6]

来源：力扣（LeetCode）

解答

直接用模拟方法会超时，而这道题归根结底是一道数学问题，数学规律归纳如下：

1. 给定大小为 n 的数字构成的 1-n 的数组，在进行一轮删除后，剩下的个数为 n / 2 （向下取整）；
2. 剩下的数组仍然是等差数组，且每次公差翻倍，即从1, 2, 4, ...
3. 剩下的数组中，要么是原数组第一个a0，要么是原数组第二个a1（即a0+公差）：

具体第一个元素规律如下：

1. 从右往左进行一轮删除，且个数为偶数个：剩下第一个元素a0
2. 其他（从左往右，无论是奇数还是偶数；或从右往左奇数个）：剩下第一个元素均为a0+公差。

具体代码如下：

class Solution {
public:
    int lastRemaining(int n) {
        int a = 1;
        int d = 1;
        int num = n;
        int dir = 1; // 1 从左往右， -1 从右往左

        while (num != 1) {
            if (!(dir == -1 && num % 2 == 0)) {
                a = a + d;
            }
            dir *= -1;
            d *= 2;
            num /= 2;
        }

        return a;
    }
};