0390-消除游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:32:52 2023-09-13 15:32:52 Updated    

列表 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

方法一：等差数列模拟

思路与算法

依照题意，我们每次都将整数列表进行间隔删除，因此每次删除后剩余的整数列表都是等差数列。假设第 $k$ 次删除后的等差数列的首元素为 $a_1^k$，末尾元素为 $a_n^k$，公差为 step}_k$，元素数目为 cnt}_k$，则第 $k+1$ 次删除后的等差数列满足：

$step}_{k+1}=\textit{step}k \times 2$$
$cnt}{k+1}=\Big\lfloor \frac{\textit{cnt}_k}{2} \Big\rfloor$$

初始时 $k=0$，表示尚未删除任何元素。

  • 如果 k 是偶数，则从左向右删除。

    • 如果元素数目 cnt}_k$ 为奇数，则两端的元素都会被删除。

    $$
    \begin{aligned}
    a_1^{k+1}&=a_1^k+\textit{step}_k \
    a_n^{k+1}&=a_n^k-\textit{step}_k
    \end{aligned}
    $$

    • 如果元素数目 cnt}_k$ 为偶数，则首端元素会被删除，末端元素不会被删除。

    $$
    \begin{aligned}
    a_1^{k+1}&=a_1^k+\textit{step}_k \
    a_n^{k+1}&=a_n^k
    \end{aligned}
    $$

  • 如果 $k$ 是奇数，则从右向左删除。

    • 如果元素数目 cnt}_k$ 为奇数，则两端的元素都会被删除。

    $$
    \begin{aligned}
    a_1^{k+1}&=a_1^k+\textit{step}_k \
    a_n^{k+1}&=a_n^k-\textit{step}_k
    \end{aligned}
    $$

    • 如果元素数目 cnt}_k$ 为偶数，则首端元素不会被删除，末端元素会被删除。

    $$
    \begin{aligned}
    a_1^{k+1}&=a_1^k \
    a_n^{k+1}&=a_n^k-\textit{step}_k
    \end{aligned}
    $$

当等差数列只剩一个元素，即 cnt}_k=1$ 时，返回首元素 $a_1^k$ 即可。

注意到末尾元素 $a_n^k$ 可以使用首元素 $a_1^k$、公差 step}_k$ 和元素数目 cnt}_k$ 表示：

$$a_n^k=a_1^k+\textit{step}_k \times (\textit{cnt}_k-1)$$

因此可以省略末尾元素 $a_n^k$。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lastRemaining(int n) {
        int a1 = 1;
        int k = 0, cnt = n, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) { // 正向
                a1 = a1 + step;
            } else { // 反向
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            cnt = cnt >> 1;
            step = step << 1;
        }
        return a1;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lastRemaining(int n) {
        int a1 = 1;
        int k = 0, cnt = n, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) { // 正向
                a1 = a1 + step;
            } else { // 反向
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            cnt = cnt >> 1;
            step = step << 1;
        }
        return a1;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int LastRemaining(int n) {
        int a1 = 1;
        int k = 0, cnt = n, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) { // 正向
                a1 = a1 + step;
            } else { // 反向
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            cnt = cnt >> 1;
            step = step << 1;
        }
        return a1;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lastRemaining(int n) {
    int a1 = 1;
    int k = 0, cnt = n, step = 1;
    while (cnt > 1) {
        if (k % 2 == 0) { // 正向
            a1 = a1 + step;
        } else { // 反向
            a1 = (cnt % 2 == 0) ? a1 : a1 + step;
        }
        k++;
        cnt = cnt >> 1;
        step = step << 1;
    }
    return a1;
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lastRemaining(self, n: int) -> int:
        a1 = 1
        k, cnt, step = 0, n, 1
        while cnt > 1:
            if k % 2 == 0:  # 正向
                a1 += step
            else:  # 反向
                if cnt % 2:
                    a1 += step
            k += 1
            cnt >>= 1
            step <<= 1
        return a1
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func lastRemaining(n int) int {
    a1 := 1
    k, cnt, step := 0, n, 1
    for cnt > 1 {
        if k%2 == 0 { // 正向
            a1 += step
        } else { // 反向
            if cnt%2 == 1 {
                a1 += step
            }
        }
        k++
        cnt >>= 1
        step <<= 1
    }
    return a1
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var lastRemaining = function(n) {
    let a1 = 1;
    let k = 0, cnt = n, step = 1;
    while (cnt > 1) {
        if (k % 2 === 0) { // 正向
            a1 = a1 + step;
        } else { // 反向
            a1 = (cnt % 2 === 0) ? a1 : a1 + step;
        }
        k++;
        cnt = cnt >> 1;
        step = step << 1;
    }
    return a1;
};

复杂度分析

  • 时间复杂度：$O(\log n)$，其中 $n$ 为初始整数列表的元素数目。每次删除都会将元素数目减半，所以时间复杂度为 $O(\log n)$。

  • 空间复杂度：$O(1)$。只需要使用常数的额外空间。

 Comments
On this page
0390-消除游戏