Bloomberg 圆桌每数到第 k 人淘汰：Josephus 递推

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版从编号 1 开始数，编号 1..n，每数到第 k 人移除，下一人从 1 继续计数。
• 若题意‘任意一人开始’表示每个起点都可能，应先澄清是给定 start、返回所有可能幸存者，还是只选择一个固定起点。

解题路线

1. 基线用循环队列删除每第 k 人，利于手算但链表/队列实现需要准确处理指针。
2. 设 J(m) 为 m 人、0-based 从 0 开始数的幸存下标；删首轮第 k 人后把剩余 m−1 人重新编号，可得 J(m)=(J(m−1)+k) mod m，J(1)=0。
3. 自 m=2 迭代到 n，最后 +1 得训练版 1-based 结果；若初始起点变为 s，则按编号环整体旋转结果。
4. 手算 n=5,k=2：淘汰 2,4,1,5，幸存 3，与递推一致。

手动走一遍

n=5,k=2 的递推下标：m=1 得 0，m=2 得 0，m=3 得 2，m=4 得 0，m=5 得 2，因此返回编号 3。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def survivor(n, k):
    """Return 1-based survivor for people numbered 1..n."""
    if n <= 0 or k <= 0:
        raise ValueError("n and k must be positive")
    index = 0
    for size in range(2, n + 1):
        index = (index + k) % size
    return index + 1

复杂度

递推 O(n) 时间、O(1) 空间；循环队列模拟通常 O(nk) 或借链表 O(n) 次删除但还要逐数移动，不能无条件说 O(n)。

易错点与追问

容易失分的边界

• 把 k 当成‘跳过 k 人再删’，造成 +1 偏差。
• 忘记 0/1 下标转换。
• 忽略从任意一人开始的歧义。
• n=0 或 k=0 未定义。

继续深挖

• 给起点 s 怎样映射？
• 若要输出完整淘汰顺序？
• n 巨大而 k=2 能否给闭式？