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完整代码如下：

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

Python完整代码如下：

# -*-coding:utf-8-*-deflast_integer(n:int)->int:mask=0xAAAAAAAAAAAAAAA# binary: ...1010return((n-1)&mask)+1defmain():n=8result=last_integer(n)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<cstdint>int64_tlastInteger(int64_tn){constint64_tmask=0xAAAAAAAAAAAAAAA;return((n-1)&mask)+1;}intmain(){int64_tn=8;int64_tresult=lastInteger(n);std::cout<<result<<std::endl;return0;}