LeetCode 390 这道题每次看到都有不少人被它的名字骗了叫什么“消除游戏”听起来像是模拟一局消除小游戏可实际上它是一道典型的数学规律题坑就在于你要是真去模拟立马会撞上规模带来的复杂度天花板。这篇文章我会用 Swift 从零开始解一遍 LeetCode 390把背后的等差数列规律拆开讲透再给出可以直接提交的题解代码。无论你是刚开始刷 LeetCode 的 Swift 选手还是想复习一下“找规律 迭代”这类套路这篇都能让你少踩几个坑。1. 先看清楚这道题到底在问什么1.1 题目规则拆解一轮一轮“删除第1个、再隔一个删”题目给了一个整数n表示一开始的数组是[1, 2, 3, ..., n]。接着无限循环做两件事直到数组只剩一个数字第一轮从左到右删除第 1 个元素然后每隔一个删一个也就是删除下标 0、2、4……的元素。第二轮从右到左从最右边的元素开始删除然后每隔一个删一个也就是删除当前数组从右往左数的第 1、3、5……个元素。之后每一轮方向都交替一次左、右、左、右……最后一轮剩下的那个数字就是答案。比如n 9时初始[1, 2, 3, 4, 5, 6, 7, 8, 9]从左删第 1、3、5、7、9 个位置剩下[2, 4, 6, 8]从右删最右边的8再隔一个删4剩下[2, 6]从左删第一个2剩下[6]所以lastRemaining(9) 6。这里最容易看走眼的地方是第二轮从右向左删除时“每隔一个”不是按数组下标从左数而是从右端开始算。很多人一上来写模拟代码时总习惯从左边下标去判断结果第二轮就把方向搞反了。1.2 有哪些坑第一次看题最容易跳进去的误区我见过不少人在这个题目上犯的错基本集中在三个点第一把“从右往左删”理解成“从右端点开始但删的是原数组偶数下标”。实际上在第二轮数组已经变成了第一轮剩下的子序列下标和原数组对不上了。正确理解应该是每一轮都有一个独立的方向删除时从该方向的端头开始隔一个删一个。第二默认了模拟法就够用。题目里n最大能到10^9数组根本开不出来哪怕开出来了每一轮还要删除一半元素光是移动元素就是灾难。所以这不是一道“能不能写出来”的题而是一道“能不能意识到必须找规律”的题。第三忽略方向交替对结果的影响。首项到底变不变取决于当前轮的方向和当前数组长度的奇偶性。这不是靠背结论就能稳的得自己手动推一遍后面我会把这条规律完整展开。2. 为什么不能直接模拟暴力解法的复杂度陷阱2.1 数组模拟方案与时间复杂度先看最直观的写法用数组存下1...n然后每一轮创建一个新数组把保留下来的元素塞进去。func lastRemaining(_ n: Int) - Int { var arr Array(1...n) var leftToRight true while arr.count 1 { var next: [Int] [] if leftToRight { for i in 0..arr.count where i % 2 1 { next.append(arr[i]) } } else { var index arr.count - 1 var keep true while index 0 { if keep { next.insert(arr[index], at: 0) } keep.toggle() index - 1 } } arr next leftToRight.toggle() } return arr[0] }这段代码在小数据下没问题但它的复杂度是 O(n) 的级别而且next.insert(arr[index], at: 0)是 O(n) 操作。每一轮数组长度减半总时间大约是 n n/2 n/4 ...接近 2n 次元素操作。看着好像“线性复杂度”也没那么差但问题是题目给出的n可以达到10^9连Array(1...n)这一步在 LeetCode 的 Swift 环境里都会直接内存爆掉。所以模拟法的真正问题不只是时间复杂度而是它一开始就不该被当作可行方案来设计。LeetCode 390 放在 medium/hard 的位置核心目的就是逼你跳出模拟思维。2.2 链表的思路也不够好那有人会想数组删除中间元素慢我用链表总行了吧链表删除确实是 O(1)但这里有两个新麻烦每一轮要从方向端点开始每隔一个结点删一个遍历链表本身是 O(n)。每一轮结束后方向要反向链表作为单向结构不方便回退用双向链表又增加内存和指针维护成本。删除一半结点后链表的“当前端点”需要维护好否则下一轮方向又错了。说白了链表只是把数组移动元素的开销换成了指针遍历的开销整体仍然是 O(n)而且实现复杂度比数组还高。我用 Swift 自己写过一版双向链表的解法调试了两个小时最后发现不仅速度慢逻辑还容易崩。结论很直接看到n 10^9就要立刻想到 O(n) 都不行必须往 O(log n) 甚至 O(1) 去靠。而 O(log n) 的来源就是“每轮元素个数减半”这件事。3. 把“删数”看成“等差数列收缩”核心规律推导3.1 每一轮剩下的数字仍然是一个等差数列这是整个题目最关键的一步。我们不需要真的维护数组中每个元素因为每一轮剩下的元素永远是一个等差数列。第一轮开始时数组是1, 2, 3, 4, 5, ...公差是 1。从左删掉奇数位置后剩下2, 4, 6, 8, ...公差变成 2首项变成 2。第二轮如果再删一部分剩下的元素还是等差的公差会继续翻倍成 4。比如[2, 4, 6, 8]从右删掉8和4后剩下[2, 6]首项 2公差 4。所以我们要维护的核心变量只有四个start当前等差数列的首项step当前公差count当前剩余元素个数leftToRight下一轮的方向每一轮结束count减半step翻倍方向翻转。整个问题就从“维护数组”简化成了“维护四个变量”复杂度立刻降到 O(log n)。3.2 什么时候“首项”会变从左删和从右删的本质区别既然序列是等差的那么每一轮之后新的首项能不能直接算出来决定了算法对不对。从左往右删时最左端的元素一定会被删除因为规则是“先删第 1 个再隔一个删”。所以新的首项必然是原来的start step。比如[1, 3, 5, 7]从左删1和5剩下[3, 7]首项从 1 变成 3。从右往左删时问题就没这么简单了。因为你是从右端开始删的最左端的start到底会不会被删取决于当前元素个数是奇数还是偶数。举个例子当前数组是[2, 4, 6, 8]长度 4。从右删删8隔一个跳过6再删4最后剩下的最左端元素是2。此时start不变还是 2。再看[2, 4, 6]长度 3。从右删删6隔一个跳过4再删2最左端的 2 被删掉了剩下的是 4。此时start要增加一个step。关键在于从右往左删时只有当长度是奇数时最左端的元素才会被删掉。这是因为从右端开始隔一个删一个右端第一个被删第二个被保留第三个被删……如果你的数组长度是奇数那么从右往左数最后一个被判断的元素索引会落在左端并且它会被删除。3.3 偶数长度与奇数长度从右侧删除的关键判断把上面的规律整理成一张表会清晰很多当前方向当前长度最左端start会被删除吗新首项从左往右任意会因为先删第 1 个start step从右往左偶数不会左端元素被保留start从右往左奇数会隔一个删一个删到左端start step所以更新首项的条件可以合并成一句话如果本轮方向是从左往右或者本轮元素个数是奇数那么新首项就是start step。这个“或者”关系很容易记错我建议你把它手推几遍再写代码。我见过很多人背结论时只记住了“从右删奇数会变”却忘了从左删无论什么情况都会变结果代码到了leftToRight true的那一轮就开始错。4. Swift 实现与逐行拆解4.1 最推荐的迭代解法O(log n) 时间O(1) 空间有了上面的规律Swift 代码可以写得很短class Solution { func lastRemaining(_ n: Int) - Int { var count n var step 1 var start 1 var leftToRight true while count 1 { if leftToRight || count % 2 1 { start step } count / 2 step * 2 leftToRight.toggle() } return start } }这套代码我实测在 LeetCode 上可以直接通过运行时间在 0ms 级别。代码里最关键的是if leftToRight || count % 2 1这一行它是 3.3 节表格的直接翻译。如果你习惯递归还有一个非常简洁的版本class Solution { func lastRemaining(_ n: Int) - Int { if n 1 { return 1 } return 2 * (n / 2 1 - lastRemaining(n / 2)) } }这个递归写法也很优雅但我觉得第一次接触这道题时迭代版本更容易和上面的规律建立联系。递归版本更适合你已经彻底理解了“第一轮后剩2, 4, ..., 2 * floor(n/2)问题等价于对称的右侧消除”之后作为第二解去感受数学的美感。4.2 为什么这个条件下要更新 start拆开每一步看我在调试这段代码时最喜欢做的一件事就是把循环里的变量打印出来逐轮对照。这里以n 10为例初始start 1step 1count 10方向从左往右。第一轮方向从左往右条件成立start step变为 2。count 5step 2方向翻转。第二轮当前start 2step 2序列是[2, 4, 6, 8, 10]count 5方向从右往左。leftToRight false但count % 2 1所以条件成立start step变为 4。这对应从右端删10、6、2剩下[4, 8]新首项确实是 4。count 2step 4方向翻转。第三轮当前start 4step 4序列是[4, 8]count 2方向从左往右。方向从左往右条件成立start step变为 8。count 1循环结束。最后返回 8。手动模拟一遍n 10从左删奇数位置剩下[2, 4, 6, 8, 10]从右删10和6剩下[4, 8]从左删4剩下[8]完全一致。我看这道题的讨论区时发现不少人会纠结“先更新start还是先更新step”。答案很明确必须在step翻倍之前用旧的step更新start。因为首项增加的量是当前轮次的公差而不是下一轮的公差。代码里先start step再step * 2这个顺序是有依据的不是随手写的。4.3 复杂度分析与边界测试时间复杂度很好算每轮count都直接除以 2循环次数最多是log2(n)级别n 10^9时约 30 次。空间上只有几个 Int 变量O(1)。边界值我建议至少测这几个输入 n预期结果说明11只有一个元素不进入循环22从左删 1剩下 232从左删 1、3剩下 242从左删 1、3剩 [2,4]从右删 4剩 296题目示例108上面推过1000000000615010758大数验证运行正常Swift 的 Int 在 LeetCode 的 64 位环境下是 64 位整数step最大也不会超过n因为step恒等于2^k而2^k n所以完全不用担心整数溢出。count / 2也是向下取整的整数除法正好符合“奇数个元素时删掉一半多一个”的事实。5. 常见问题与排查经验5.1 leftToRight 标志写反导致答案错乱这是我最初调试时踩的第一个坑。我一开始把方向的初始值设成了false因为想着第一轮从左删但代码里循环体每次开始前先判断标志结果第一轮就变成了从右删答案直接错。排查思路很简单用一个n 5的小用例跟着代码走一遍。n 5的正确结果是 2如果你把方向标志写反第一轮从左删变成了从右删结果会变成 3一下子就暴露了。建议在写循环时把方向语义和实际行为对应清楚leftToRight true代表“本轮从左往右删”在更新完start后再toggle()让标志精确对应下一轮。5.2 从右删除时奇偶判断弄反另一类常见错误是只写了if count % 2 1忘了合并左到右的情况。结果当leftToRight true但count是偶数时start没有被更新答案就会偏小。我记得有个很典型的现象这种写法在n 1到n 4时可能是对的因为前几轮刚好有规律恰好覆盖错误但一旦到了n 6、n 8答案就开始错。所以建议你准备一张“小规模手算表”比如n 1到n 12的正确答案写完代码立刻对照能省很多排查时间。5.3 递归写法的栈深度与溢出问题递归版本lastRemaining(n / 2)的递归深度只有O(log n)当n 10^9时深度约 30 层完全不会爆栈。但需要注意 Swift 默认没有尾递归优化所以哪怕逻辑上是尾递归也只是“看起来优化了”实际依然会建立调用栈。这道题的深度很小不构成问题但如果你把它推广到别的递归场景还是优先考虑迭代版本更稳。另外递归公式里出现了n / 2 1这里的除法是整数除法。比如n 5时n / 2 2对应第一次从左删除后剩下[2, 4]正好是两个元素。我在纸上推导时容易默认成2.5一旦用浮点思维去看这段代码就会懵所以特别提醒一下。5.4 测试用例与提交经验LeetCode 提交前建议在本地跑下面这组用例覆盖各种奇偶长度和边界let s Solution() print(s.lastRemaining(1)) // 1 print(s.lastRemaining(2)) // 2 print(s.lastRemaining(3)) // 2 print(s.lastRemaining(4)) // 2 print(s.lastRemaining(5)) // 2 print(s.lastRemaining(6)) // 4 print(s.lastRemaining(7)) // 4 print(s.lastRemaining(8)) // 6 print(s.lastRemaining(9)) // 6 print(s.lastRemaining(10)) // 8 print(s.lastRemaining(1000000000)) // 615010758如果你用的是 Xcode Playground最后一行大数测试可能会因为编译速度稍慢但不影响结果。真正提交到 LeetCode 时性能完全没问题。我还想分享一个调题思路如果代码跑出来错了别急着看题解先把n从 1 开始的每个答案打印出来再和手算结果对比。找到第一个不一致的n用那个规模去逐步打印每一次循环里的start、step、count、leftToRight基本两分钟内就能定位是条件判断的问题还是更新的顺序问题。这比盯着代码干想要快得多。回到 LeetCode 390 本身这道题给我最大的感触是它把“看似要模拟、实则要推理”的设计玩得很妙。你一旦看穿序列永远是等差数列这一点代码反而只有十几行。Swift 的语法表达这种迭代逻辑很舒服toggle()切方向、start step更新首项读起来就是一段流畅的数学推导过程。如果你刷题时被这类规律题卡住不妨记住这个经验遇到大规模删除或变化的题目先别急着写模拟停下来看看每一步之后剩下的东西是不是保持了某种结构往往那个结构就是你通向 O(log n) 解法的钥匙。