Swift 解 LeetCode 390：消除游戏的数学规律与 O(log n) 优化

我第一次见“LeetCode 390 消除游戏”这道题的时候第一反应是这不就是模拟吗维护一个数组从左往右删一轮再从右往左删一轮循环到只剩一个数就完事。然后我看了眼数据范围n 最大能到 10^9瞬间清醒。Swift 里Array(1...1_000_000_000)这一行就能让内存和时限一起爆炸。所以这道题标着 Medium实际上考的完全不是“会不会写循环”而是“能不能看穿消除过程背后的数学结构”。这篇文章我就用 Swift 把这道题的规律推导、代码实现、边界陷阱完整拆一遍顺便分享一个很实用的对拍脚本适合正在刷 LeetCode 的 Swift 选手也适合准备面试时想搞清楚“为什么暴力解不行”的人。1. 为什么暴力解法在 n 10^9 面前直接阵亡1.1 暴力模拟的复杂度其实不算差但依然不够看很多人以为暴力解法是 O(n^2)其实不是。你每次把数组长度减半遍历的元素总量加起来是 n n/2 n/4 ... 等比数列求和约等于 2n。所以单纯从遍历次数看暴力解法是 O(n)。问题在于 n 的上限是 10^9。Swift 一秒大概能执行几千万到一亿次简单操作2n 意味着大约 20 亿次操作在 LeetCode 的时限下基本是几十秒级别。更要命的是内存一个包含 10^9 个 Int 的数组在 64 位平台上直接占 8GB 内存LeetCode 的 Swift 环境根本不可能分给你这么多空间。我最初在 Playground 里试了let arr Array(1...100_000_000)几乎是瞬间内存暴涨然后被系统杀掉。所以这条路从根上就走不通。1.2 关键观察每轮剩下的序列依然是等差数列暴力为什么浪费因为每一轮我们其实不需要知道“具体哪些数剩下了”只需要知道“剩下的序列长什么样”。仔细观察第一轮从 1 开始每隔一个删一个剩下的是 2, 4, 6, 8, ... 这是一个首项为 2、公差为 2 的等差数列。第二轮从右往左删假设当前序列是 [2, 4, 6, 8, 10, 12]从右往左每隔一个删一个删掉的是 12、8、4剩下的是 2、6、10这依然是等差数列首项 2、公差 4。第三轮从左往右删剩下 6还是等差数列只是只剩一项罢了。这个观察是整个题解的基石任何一轮操作之后剩余序列都能用一个“首项 公差 项数”的三元组完整描述。我们真正要求的就是“最终首项”的值。既然如此完全没必要把整个数组搬来搬去。2. 把序列压缩成三元组首项、公差、项数的变化规则2.1 三个状态变量的定义设当前序列为a序列的第一个元素d公差也就是相邻两个元素的间隔cnt序列中元素的个数初始状态是a 1、d 1、cnt n。每一次消除操作之后项数会减半cnt cnt / 2向下取整公差会翻倍d 2 * d因为删掉一半元素后两个保留元素之间隔了两个原公差唯一需要仔细推导的是首项a到底变不变、怎么变。2.2 首项变化的唯一难点从右往左删时要看奇偶从左往右删除时规律非常稳定删除第 1、3、5... 项剩下的第一个元素是从左往右数第 2 个也就是原来的a d。这个结论跟cnt是奇数还是偶数没有关系。但从右往左删除时情况就微妙了如果cnt是偶数比如 [2, 4, 6, 8]从右往左每隔一个删一个删掉 8、4剩下 2、6。首项 2 没有被删依然保留所以a不变。如果cnt是奇数比如 [2, 4, 6, 8, 10]从右往左每隔一个删一个删掉 10、6、2首项 2 被删掉了剩下的第一个元素变成 4所以a a d。结合两种情况判断条件可以合并成一句当fromLeft true或cnt % 2 1时a a d否则a保持不变。2.3 用 n 8 完整走一遍推导拿 n 8 来验证这个规则初始序列 [1, 2, 3, 4, 5, 6, 7, 8]三元组是 a1, d1, cnt8方向是从左往右。第一轮从左往右删删除 1、3、5、7剩 [2, 4, 6, 8]。计算cnt 变成 4d 变成 2首项 a 因为是从左往右所以 a 1 1 2。第二轮从右往左删当前 cnt4 是偶数首项不变a 还是 2。剩 [2, 6]此时 d 变成 4cnt 变成 2。第三轮从左往右删a 2 4 6。cnt 变成 1循环结束。最终答案就是 6。手动模拟一下确实是 6没问题。2.4 另一种等价的极短递归公式上面这套三元组迭代法已经很清晰了不过 LeetCode 讨论区还有一种更“吓人”的递归写法func lastRemaining(_ n: Int) - Int { if n 1 { return 1 } return 2 * (n / 2 1 - lastRemaining(n / 2)) }我第一次看到这个公式时愣了半天后来想明白了。核心思路是“映射”第一轮从左往右删除奇数位置后剩下的序列是 [2, 4, 6, ..., 2 * m]其中 m n / 2。整体除以 2 之后问题就变成在 [1, 2, ..., m] 上从右往左开始做同样的消除。而从右往左开始消除的结果恰好等于 m 1 减去从左往右开始消除的结果因为把序列镜像对称之后删除规则就反过来了。所以f(n) 2 * (m 1 - f(m))。这个公式非常优雅但理解和记忆成本比迭代三元组高。日常写题我更推荐迭代版不容易在递归边界上翻车。3. Swift 实现核心代码、逐行拆解与 Int 溢出防线3.1 可提交的完整代码先给出可以直接粘贴到 LeetCode 的代码class Solution { func lastRemaining(_ n: Int) - Int { var first 1 var diff 1 var count n var fromLeft true while count 1 { if fromLeft || count % 2 1 { first diff } diff * 2 count / 2 fromLeft.toggle() } return first } }整个函数只有十几行时间复杂度和空间复杂度分别如下时间复杂度 O(log n)因为每轮 count 减半空间复杂度 O(1)只用了几个变量n 取 10^9 时循环次数大约是 30 次这个性能在 Swift 里可以忽略不计。3.2 更新顺序是很多人写错的重灾区这个代码看起来短但有一个隐藏的坑first diff的判断必须基于“当前轮”的 count 和 fromLeft不能先更新 count 再判断。我举个例子你就明白了。假设 n 12初始 [1...12]第一轮从左往右删剩 [2, 4, 6, 8, 10, 12]此时 a2, d2, cnt6。第二轮从右往左删cnt6 是偶数所以首项应该保持 2。如果你在判断之前先执行了count / 2count 变成 33 % 2 1就会错误地把 first 变成 4最终结果直接崩掉。所以正确的顺序必须是用当前 count 判断首项要不要变再更新 diff 和 count最后翻转方向每轮循环里这三步的顺序只要错一个答案就歪了。3.3 Int 溢出与位运算优化Swift 的Int在 64 位平台上占 64 位取值范围非常大。这道题的 diff 初始为 1每轮乘以 2n 最大 10^9 时 diff 最多到 2^30 左右完全在安全范围内。但如果把这段代码移植到 32 位平台比如某些嵌入式 Swift 环境diff 在 n 超过 2^30 时就会溢出。LeetCode 的 Swift 环境是 64 位可以放心但作为一个严谨的题解我还是建议用位运算把风险降到最低if fromLeft || count 1 1 { first diff } diff 1 count 1count 1 1等价于count % 2 1diff 1等价于diff * 2count 1等价于count / 2。位运算除了效率更高还明确告诉读者这里就是在操作二进制位级别的状态变化。3.4 函数式风格的替代方案如果你偏好简洁也可以把状态打包成一个元组用递归写func lastRemaining(_ n: Int) - Int { func f(_ first: Int, _ diff: Int, _ count: Int, _ fromLeft: Bool) - Int { if count 1 { return first } let newFirst (fromLeft || count % 2 1) ? first diff : first return f(newFirst, diff 1, count 1, !fromLeft) } return f(1, 1, n, true) }递归深度是 O(log n)完全不用担心栈溢出。两种写法在 LeetCode 上都能过选自己顺手的那种就行。4. 边界用例、反直觉陷阱和一个对拍脚本4.1 从 n 1 到 n 10 的规律表写这类规律题建议先把小规模的结果手工列出来看有没有明显模式。我用暴力模拟跑了前 10 个值n结果112232425264748696108这个表最直观的价值是验证推导是否正确。比如 n8 时结果是 6n10 时结果是 8都跟我们在 2.3 节手算的结果对得上。还有一个容易忽略的点n1 时循环压根不执行直接返回 first1。这个边界虽然简单但如果你把循环条件写成while count 1就会变成死循环。4.2 两个反直觉的坑第一个坑是“从右往左删且 cnt 为偶数时首项不变”。很多人会想当然地认为从右往左删肯定会动到第一个元素于是每次都让 first diff。只有在 cnt 为奇数时从右往左才会把首项删掉这个反直觉点不亲自推一遍很难记住。第二个坑是递归公式里的整数除法。lastRemaining(n / 2)的 n / 2 是向下取整Swift 的整数除法对正数本来就是向下取整但如果你改写的时候不小心用了ceil或者浮点数除法结果就会错。整数运算在算法题里是默认规则可一旦代码从整数改成浮点就会出现精度问题。4.3 对拍脚本用暴力解验证数学解我刷题有一个习惯凡是用数学规律写的题必须写一个暴力解作为“对照实验”。Xcode Playground 里用暴力解跑小数据用数学解跑同样的小数据逐项比对。下面这个脚本可以直接跑func bruteForce(_ n: Int) - Int { var arr Array(1...n) var fromLeft true while arr.count 1 { if fromLeft { arr stride(from: 1, to: arr.count, by: 2).map { arr[$0] } } else { let newArr stride(from: arr.count - 2, through: 0, by: -2).map { arr[$0] } arr newArr.reversed() } fromLeft.toggle() } return arr[0] } for n in 1...100 { let expected bruteForce(n) let actual lastRemaining(n) if expected ! actual { print(Mismatch at n\(n): expected \(expected), got \(actual)) break } }这里有个细节从右往左删的时候我把保留的元素先反向收集再reversed()这样才能得到从左到右的正确顺序。注意不是arr.count - 1开始收集因为从右往左每隔一个删一个第一个被删的是最右边的元素第一个被保留的是右边第二个对应索引arr.count - 2。这个细节我一开始就写错了对拍脚本立刻帮我揪了出来。暴力解在 n 超过 10000 时会明显变慢所以只用来验证小数据就够。数学解的每一轮推导是否正确都可以靠这个小脚本迅速确认。5. 这类“假装是模拟”的题到底在考什么5.1 方法论用一个状态变量组描述整个序列LeetCode 390 表面上是一个模拟题实际上是一个“状态压缩”题。它真正考察的能力是你能不能发现虽然序列很长但每一轮之后整个序列的信息量并没有爆炸只需要少数几个变量就能完全描述。这种思维方式在算法题里非常常见。比如线段树用节点区间描述大数组快速幂用底数和指数描述幂运算约瑟夫环用“当前起点 人数 步长”描述圆桌状态。遇到“给你一个很大的结构反复做某种操作”的题目我的第一反应永远是能不能用一个或者几个变量把这个结构在每次操作后的“不变量”抓住对这道题来说不变量就是“剩余序列仍然是等差数列”。只要抓住这个复杂度就从 O(n) 降到了 O(log n)。5.2 同类题的横向对比LeetCode 上还有几道题和 390 的思考方式很像LeetCode 1823约瑟夫环也是用一个“当前位置 剩余人数”递推而不是真的去删除数组元素。LeetCode 1351 / 378 这类矩阵题用“起点在右上角慢慢挪”代替二维遍历。LeetCode 50实现 pow(x, n)用快速幂把乘法次数从 O(n) 降到 O(log n)。它们的共同点都是不要用第一直觉去模拟完整过程先想想能不能用数学结构压缩状态。从刷题效率的角度看这比多背模板有用得多。5.3 给 Swift 刷题党的几点建议Swift 在某些 LeetCode 题里确实没 C 或者 Python 那么顺手但它也有一些独特优势。就拿这道题来说toggle()方法翻转布尔值语义比fromLeft !fromLeft更清晰。位运算符、、在 Swift 里类型要求严格不会出现整型隐式转换的坑。元组和递归天然契合适合写 3.4 节那种函数式风格。我自己做这道题的心得是花 10 分钟手推规律比花 10 分钟写一个注定超时的暴力模拟要值。先用小 n 打表再用对拍脚本验证最后再整理成 Swift 代码提交整个过程下来你对等差数列和状态压缩的理解会比单纯背题解深得多。最后分享一个小技巧以后遇到任何“每轮去掉一半元素”的题先画一个 n8 或者 n10 的执行过程图把每一轮的剩余序列写出来很多规律会自己跳出来。LeetCode 390 这个题我能在几分钟内写出最优解靠的就是这张手写推演表。