题目

给定一个从1 到 n 排序的整数列表。 首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。 第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。 我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 返回长度为 n 的列表中，最后剩下的数字。

示例

1
2
3
4
5
6
7
8
9

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

解答

暴力模拟超时，看了一下别人的思路。

通过观察用例，我们可以得到以下规律：

  1. 经历的回合数应该是 $$\lfloor \log_2n \rfloor + 1$$
  2. arr数组永远是一个等差数列
  3. arr数组的数目，每次减少一半（向下取整）
  4. 公差每次翻倍

我们知道一个等差数列可以由a0（首项）, d（公差）, n（数列元素个数）三个参数来定义。

综合以上规律，我们知道每次删除后，以上三个参数每次应该这样变化

  • d → 2d
  • n → n/2
  • a0→a0 或者a0→a0+d

大体上来说这道题目就是这样，其它细节可以看代码。

如何决定a0的变化？当删除数字时，存在以下四种情况：

  1. 从左向右删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
  2. 从左向右删除，总共有偶数个数字（第一位要删掉，最后一位不用删掉）
  3. 从右向左删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
  4. 从右向左删除，总共有偶数个数字（第一位不用删掉，最后一位要删掉）

只有情况4才会出现a0→a0，其余都是a0→a0+d

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int lastRemaining(int n) {
    int num_amount = n;
    int loop_cnt = 0;
    int a0 = 1, d = 1;
    while (num_amount != 1) {
        // 奇数个数字
        if (num_amount % 2 == 1) {
            a0 = a0 + d;
        }
            // 偶数个数字
        else if (num_amount % 2 == 0) {
            bool left_to_right = (loop_cnt % 2 == 0);
            if (left_to_right) {
                a0 = a0 + d;
            } else
                a0 = a0;
        }
        loop_cnt++;
        d *= 2;
        num_amount /= 2;
    }
    return a0;
}

参考文章

C++ 数学+找规律 - 消除游戏 - 力扣（LeetCode） (leetcode-cn.com)