Swift算法
LeetCode 390 消除游戏 Swift 算法解析
本题要求模拟从 1 到 n 的整数列表交替左右消除过程，直至剩一个数。由于 n 可达 10^9，直接模拟效率低。核心思路是利用数学规律：每轮消除后剩余数字构成等差数列。通过维护头元素 head、步长 step 和数量 count，可在 O(log n) 时间内推算结果。代码使用 Swift 实现，逻辑简洁且空间复杂度为 O(1)。适用于约瑟夫问题变种及大规模数据分批处理场景。
本题要求模拟从 1 到 n 的整数列表交替左右消除过程，直至剩一个数。由于 n 可达 10^9，直接模拟效率低。核心思路是利用数学规律：每轮消除后剩余数字构成等差数列。通过维护头元素 head、步长 step 和数量 count，可在 O(log n) 时间内推算结果。代码使用 Swift 实现，逻辑简洁且空间复杂度为 O(1)。适用于约瑟夫问题变种及大规模数据分批处理场景。
这道题其实挺有意思的，它要求我们模拟一个交替从左到右、从右到左的消除过程，最后找出剩下唯一一个数字。听起来像是约瑟夫问题的变种，但实际上可以通过数学规律来高效解决。
由于 n 最大可以到 10^9，如果直接模拟整个消除过程，时间和空间都会爆炸。我们需要找出其中的规律：每一轮消除后，剩余数字形成一个等差数列，我们只需要维护"头元素"和"步长"，就能推算出下一轮的状态，而不需要真正维护整个数组。
题目要求是这样的：列表 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 <= 10^9这道题的核心思路是：每一轮消除后，剩余数字构成一个等差数列。我们只需维护当前等差数列的"头元素"和"步长"，以及剩余数量，就能用 O(log n) 的时间推算出最终答案，而不需要真正模拟整个数组。
下面是完整的 Swift 解决方案：
class Solution {
func lastRemaining(_ n: Int) -> Int {
if n == 1 {
return 1
}
// head: 当前剩余序列的第一个元素
var head = 1
// step: 相邻剩余元素之间的差值（等差数列的公差）
var step = 1
// count: 剩余元素的数量
var count = n
// leftToRight: 本轮是否从左到右消除
var leftToRight = true
while count > 1 {
if leftToRight {
// 从左到右：总是会删除第一个元素，所以 head 要后移
head += step
} else {
// 从右到左：只有当剩余数量为奇数时，才会删到第一个元素
if count % 2 == 1 {
head += step
}
}
step *= 2
count /= 2
leftToRight.toggle()
}
return head
}
}
让我们一步步分析这个解决方案。
每一轮消除后，剩余数字都形成一个等差数列。例如 n=9 时：
[1, 2, 3, 4, 5, 6, 7, 8, 9]，头=1，步长=1，数量=9[2, 4, 6, 8]，头=2，步长=2，数量=4[2, 6]，头=2，步长=4，数量=2[6]，头=6，步长=8，数量=1我们只需要维护 head（头元素）、step（步长）、count（剩余数量），就能完整描述当前状态，无需保存整个数组。
从左到右消除时，我们总是先删掉第一个元素，然后每隔一个删一个。因此，无论剩余数量是奇数还是偶数，原来的第一个元素都会被删掉，新的第一个元素就是原来的第二个元素。
由于剩余序列是等差数列，相邻元素相差 step，所以新的 head 为 head + step：
if leftToRight { head += step }
从右到左消除时，我们先删最右边，再每隔一个删。这时头元素是否被删，取决于剩余数量的奇偶性。
count 为偶数：例如 [2, 4, 6, 8]，从右删 8、4，剩下 [2, 6]，头 2 保留，head 不变count 为奇数：例如 [2, 4, 6]，从右删 6、2，剩下 [4]，头 2 被删，新的头是 4，head 需要加上 step所以：
if !leftToRight {
if count % 2 == 1 {
head += step
}
}
每轮消除后，相邻剩余元素之间的间隔会翻倍，因此 step *= 2。剩余数量大约减半，所以 count /= 2：
step *= 2
count /= 2
leftToRight.toggle()
当 n == 1 时，直接返回 1，无需进入循环。
执行过程：
结果： 6
执行过程：
结果： 1
模拟过程：
[1,2,3,4,5,6][2,4,6][4]算法过程：
模拟过程：
[1,2][2]算法过程：
时间复杂度：O(log n)
每一轮 count 约减半，因此循环次数约为 log₂(n)。对于 n = 10^9，大约 30 次循环即可结束。
空间复杂度：O(1)
只使用了 head、step、count、leftToRight 等少量变量，与 n 无关。
这种'用数学规律替代模拟'的思路在实际开发中很有用：
经典的约瑟夫问题也是每隔 k 个人淘汰一人，最后剩下谁。同样可以不用模拟，而用递推或公式计算。
当数据量巨大且处理规则有规律时（如每隔一批保留一批），可以像本题一样抽象成 head、step、count，避免真正构建和遍历整个序列。
某些回合制游戏每轮按固定规则淘汰角色，若规则呈现周期性或可归纳的数学规律，可以用类似方式在 O(log n) 时间内算出结果。
本题的关键在于发现：每轮消除后剩余数字构成等差数列，只需维护头元素、步长和数量，就能在 O(log n) 时间和 O(1) 空间内得到最终结果。
要点总结：
算法优势：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online