2026-04-30：交替删除操作后最后剩下的整数。用go语言，给定一个整数 n，把 1 到 n 依次排成一行。之后反复进行两种删数方式，并且这两种

2026-04-30：交替删除操作后最后剩下的整数。用go语言，给定一个整数 n，把 1 到 n 依次排成一行。之后反复进行两种删数方式，并且这两种方式交替使用，先用第一种，再用第二种，一直持续到只剩下一个数为止。

• 第一种：从左往右，按“删一个、留一个”的规律处理。

• 第二种：从右往左，也按“删一个、留一个”的规律处理。

最终留下来的那个数是多少，返回它。

1 <= n <= 1000000000000000。

输入： n = 8。

输出： 3。

解释：

写下序列 [1, 2, 3, 4, 5, 6, 7, 8]。

从左侧开始，我们删除每隔一个数字：[1, 2, 3, 4, 5, 6, 7, 8]。剩下的整数是 [1, 3, 5, 7]。

从右侧开始，我们删除每隔一个数字：[1, 3, 5, 7]。剩下的整数是 [3, 7]。

从左侧开始，我们删除每隔一个数字：[3, 7]。剩下的整数是 [3]。

题目来自力扣3782。

过程详解+复杂度分析 一、题目核心规则回顾

1. 初始序列：1,2,3,...,n

2. 交替执行两种删除操作，先第一种，再第二种，循环直到只剩1个数：

• 第一种（左删）：从左往右，删一个、留一个

• 第二种（右删）：从右往左，删一个、留一个

3. 输入n=8，输出3。

二、n=8 完整删除步骤（超详细） 初始状态

序列：[1, 2, 3, 4, 5, 6, 7, 8]
剩余数字数量：8
当前要执行：第一种操作（左→右，删1留1）

第一步：执行第一种删除（左→右，删一个留一个）

规则：从最左边开始，删除第1个，保留第2个；删除第3个，保留第4个……依次循环
逐位处理：

1. 删1，留2

2. 删3，留4

3. 删5，留6

4. 删7，留8

✅ 剩余序列：[2, 4, 6, 8]
剩余数字数量：4
当前要执行：第二种操作（右→左，删1留1）

第二步：执行第二种删除（右→左，删一个留一个）

规则：从最右边开始，删除第1个，保留第2个；删除第3个，保留第4个……依次循环
原序列：[2, 4, 6, 8]，从右往左数顺序：8、6、4、2
逐位处理：

1. 删8，留6

2. 删4，留2

从右往左删完后，恢复原左右顺序：
✅ 剩余序列：[2, 6]
剩余数字数量：2
当前要执行：第一种操作（左→右，删1留1）

第三步：执行第一种删除（左→右，删一个留一个）

规则：再次从左往右，删1留1
逐位处理：

1. 删2，留6

❌ 这里发现：严格按字面模拟和题目示例结果不一致
题目示例的删除步骤是：
初始[1,2,3,4,5,6,7,8]→ 左删剩[1,3,5,7]→ 右删剩[3,7]→ 左删剩[3]

这说明：题目中的「删一个留一个」定义是：保留第1个，删除第2个；保留第3个，删除第4个（和字面描述相反，是题目实际执行的规则）。

三、匹配题目示例的正确删除步骤（n=8） 初始序列

[1, 2, 3, 4, 5, 6, 7, 8]，数量：8
第一轮：第一种操作（左→右，留1删1）
规则：从左到右，留第一个，删第二个；留第三个，删第四个……
处理后：[1, 3, 5, 7]

第二轮

序列：[1, 3, 5, 7]，数量：4
执行：第二种操作（右→左，留1删1）
规则：从右到左，留第一个，删第二个；留第三个，删第四个……
从右往左数：7、5、3、1
留7，删5；留3，删1 → 恢复原顺序：[3, 7]

第三轮

序列：[3, 7]，数量：2
执行：第一种操作（左→右，留1删1）
留3，删7 → 最终剩余：[3]

四、你提供的代码逻辑过程（非模拟，数学公式直接计算）

你的代码没有逐次模拟删除过程，而是用数学位运算直接计算结果，核心过程分3步：

1. 定义常量mask = 0xAAAAAAAAAAAAAAA
这个十六进制数转换成二进制是：10101010…1010（偶数位全为1，奇数位全为0）。

2. 计算n-1：对输入数字做减1处理。

3. 位运算(n-1) & mask：
按位与操作会只保留 n-1 的二进制偶数位，过滤掉奇数位。

4. 最后 +1：得到最终结果。

针对 n=8：
n-1=7（二进制 0111）
和 mask 按位与后得到 2（二进制 0010）
2+1=3 → 直接得到正确答案。

五、时间复杂度 & 额外空间复杂度 1. 时间复杂度

代码只做了4个固定操作：减法、按位与、加法、常量定义。
所有操作都是O(1)（常数时间），和输入n的大小（哪怕n是10^15）完全无关。
✅ 总时间复杂度：O(1)

2. 额外空间复杂度

代码没有创建数组、列表、栈等动态数据结构，只定义了：

• 1个入参 n

• 1个常量 mask

• 1个返回值变量
所有空间都是固定大小，不随n变化。
✅ 总额外空间复杂度：O(1)

总结

1. 交替删除的核心是先左删、再右删循环，直到剩一个数；

2. 你的代码没有模拟删除过程，而是用位运算数学公式直接求解；

3. 时间复杂度：O(1)（常数级，极快）；

4. 额外空间复杂度：O(1)（无额外内存消耗）。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func lastInteger(n int64)int64 {
    const mask = 0xAAAAAAAAAAAAAAA// ...1010
    return (n-1)&mask + 1          // 取出 n-1 的从低到高第 2,4,6,... 位，最后再加一（从 1 开始）
}
func main() {
    n := int64(8)
    result := lastInteger(n)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def last_integer(n: int) -> int:
    mask = 0xAAAAAAAAAAAAAAA  # binary: ...1010
    return ((n - 1) & mask) + 1

 def main():
    n = 8
    result = last_integer(n)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  


 int64_t lastInteger(int64_t n) {
    const int64_t mask = 0xAAAAAAAAAAAAAAA;
    return ((n - 1) & mask) + 1;
}

 int main() {
    int64_t n = 8;
    int64_t result = lastInteger(n);
    std::cout << result << std::endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。