面试题62：圆圈中最后剩下的数字

从“第3个数字到底是2还是3”开始

数字0、1、2、3、4排成圆圈，从0开始报数，0本身算第1个，1是第2个，2是第3个，所以m等于3时首次删除2。删除后不回到0，而是从2的后继3重新把它算作第1个。

这种“n个元素围成环，重复删除报数到第m个元素，直到只剩一个”的模型称为约瑟夫环。本题要求的是原始编号0到n-1中“圆圈中最后剩下的数字”，不是最后一轮中的临时下标。

先预测n等于5、m等于3的删除序列，再看模拟：若第一项写成3，说明把“从0开始”误解成“走3步后删除”；若每轮又从0开始，说明忘了删除后的后继才是下一轮起点。

方法一：用链表直接模拟圆圈

作者把0到n-1依次放入std::list，让指向begin。每轮先前进m-1次，每次到end就绕回begin；此时current正好指向本轮要删的。

删除前必须保存被删节点的后继；若后继是end，则绕到begin。作者先对current前置递增得到next，再把current减回待删节点，调用erase，最后让current指向next。

int LastRemaining_Solution1(
    unsigned int n,
    unsigned int m) {
    if (n < 1 || m < 1)
        return -1;
 
    std::list<int> numbers;
    for (unsigned int i = 0;
         i < n;
         ++i) {
        numbers.push_back(
            static_cast<int>(i));
    }
 
    auto current = numbers.begin();
    while (numbers.size() > 1) {
        for (int i = 1;
             i < m;
             ++i) {
            ++current;
            if (current == numbers.end())
                current = numbers.begin();
        }
 
        auto next = ++current;
        if (next == numbers.end())
            next = numbers.begin();
 
        --current;
        numbers.erase(current);
        current = next;
    }
 
    return *current;
}

当待删节点是链表末尾时，前置递增让current成为end，next随后改成begin；对非空list的end执行减一回到末尾是合法的，因此erase删除原末尾节点。写现代代码时更清晰的方式是先保存victim，再单独推进和环绕current。

n等于5、m等于3时，删除序列为2、0、4、1，最后剩3。每轮current都是新起点，不是容器begin；这条状态是模拟正确性的核心。

作者每次删除前实际走m-1个节点，共删除n-1次，因此时间O(nm)，建表和存储空间O(n)。list的erase本身是O(1)，但不能掩盖寻找删除位置的移动成本。官方n等于4000、m等于997大约需要四百万次迭代器前进，仍可运行，但远慢于数学法的3999轮。

可以把每轮步数先化为(m - 1) % numbers.size()，避免无意义地绕很多整圈；由于链表仍要线性走到目标，最坏总时间降为O(n平方)，空间仍是O(n)。

删除后为何要重新编号

第一次删除旧编号k后，下一轮从旧编号k+1开始。为了把剩余n-1个元素看成同样形式的子问题，把这个后继改名为新编号0，随后依次命名1到n-2。这一步称为。

以n等于5、m等于3为例，k等于2。新0、1、2、3分别对应旧3、4、0、1：

从新编号x恢复旧编号时，需要加上新0在旧环中的位置k+1，再对n取模。由于k等于m-1对n取模，k+1与m在模n意义下相同。

这个把缩小问题答案恢复到上一层坐标的过程称为。偏移是m而不是m-1，正是因为新0位于被删元素的后一个位置。

从子问题得到递推公式

令f(n,m)表示0到n-1按规则淘汰后的最终原编号。只有一个数字时，它只能是0；n个数字首次删除后，剩余环按新编号构成同参数m、规模n-1的子问题，答案是f(n-1,m)，再用逆向映射恢复。

这就是原章的“递推f(n,m)=(f(n-1,m)+m)%n”。它不是凭经验记忆的公式，而是“删除、后继重编号、加m映回”三步的直接结果。

必要的计数约定已经编码在公式里：输入编号是0到n-1，当前元素算第1个，删除后从后继开始。如果题目改成走m步后删除，或从1到n编号，公式和输出转换都必须相应调整。

方法二：从规模1逐层反推

递归定义可以自顶向下调用，但每层只依赖上一规模的一个整数，没必要保存调用栈。作者令last等于0，然后让规模i从2增长到n，每轮执行加m取模。

int LastRemaining_Solution2(
    unsigned int n,
    unsigned int m) {
    if (n < 1 || m < 1)
        return -1;
 
    int last = 0;
    for (int i = 2; i <= n; ++i)
        last = (last + m) % i;
 
    return last;
}

这个方向正是“从1个数字反推”：规模1的幸存者为0，依次恢复规模2、3直到n。时间O(n)，额外空间O(1)，也完全不创建圆圈。

n等于5、m等于3时，last依次为0、1、1、0、3。规模4时结果回到0并不表示原始数字0已经复活，它只是“规模4那一层坐标中的编号0”；下一轮映射后才得到原始规模5的编号3。

递推正确性的归纳视角

基例n等于1显然正确。假设f(n-1,m)能返回删除并重编号后的子环幸存者；n规模的首次删除只改变坐标原点，不改变后续“每次删除第m个”的相对规则，所以剩余过程与n-1子问题同构。通过phi映回旧编号就得到f(n,m)，归纳成立。

这份证明也解释了为什么只保存last足够：每层历史删除顺序都被压缩成“较小规模幸存者在当前重编号中的位置”。这种只保留递推所需最小状态的做法称为。

模拟法适合输出完整淘汰序列或验证小样本；递推法适合只求最终数字。需求不同，不应因为递推更快就声称链表法没有教学或调试价值。

输入边界与整数风险

两种作者函数都以unsigned int接收n和m，却返回-1表示无效。n等于0或m等于0时检查有效；但调用者若把负数直接转换为unsigned，会得到很大的正数，入口无法识别原始负值。公共接口更适合先用有符号或更宽类型验证，再进入无符号计算。

n等于1且m为任意正数时，两种方法都返回0。m等于1时每轮立即删除当前起点，0、1直到n-2依次离开，最终答案为n-1；递推也会产生f(i,1)=i-1。

作者数学式中的last为int、m为unsigned int，last + m按无符号算术计算。普通测试安全，但接近类型上限时加法可能先回绕，再取模i，结果不等价于数学整数加法。链表法的内层计数变量是int而m为unsigned；m超过INT_MAX时，i自增还可能触发有符号溢出。

现代版本可用64位数保存参数和中间和，并先对当前规模取m的余数。若要支持接近64位上限的n，还需无溢出的模加；常规可分配或可迭代规模下，下面的范围已经充分。

#include <cstdint>
#include <optional>
 
std::optional<std::uint64_t>
lastRemaining(std::int64_t n,
              std::int64_t m) {
    if (n < 1 || m < 1)
        return std::nullopt;
 
    const auto size =
        static_cast<std::uint64_t>(n);
    const auto step =
        static_cast<std::uint64_t>(m);
 
    std::uint64_t last = 0;
    for (std::uint64_t i = 2;
         i <= size;
         ++i) {
        const std::uint64_t offset =
            step % i;
        last = (last + offset) % i;
    }
    return last;
}

在这个循环中last与offset都小于i，常规有符号输入上限使二者之和可由uint64容纳。若接口直接接受完整uint64范围，可用条件减法或更宽整数实现模加。

六组官方测试如何互证

作者Test对每组输入同时调用链表法与递推法，并分别与同一个expected比较。这样不仅检查答案，也让两条实现路径互相约束。

Test1的5、3得到3，Test2的5、2得到2；Test3让m等于7大于n，验证环绕；Test4让m等于当前初始整圈长度6；Test5用0、0得到-1；Test6用4000、997得到1027，拉开两种复杂度的差距。

官方测试未覆盖n等于1、m等于1、只有一个参数为0、负数转换、接近整数上限或完整删除序列。现代测试应为输入契约补齐这些边界，并让小规模递推结果与独立模拟逐项对拍。

#include <cassert>
#include <cstdint>
#include <list>
 
void testLastRemaining() {
    assert(lastRemaining(5, 3) == 3);
    assert(lastRemaining(5, 2) == 2);
    assert(lastRemaining(6, 7) == 4);
    assert(lastRemaining(6, 6) == 3);
    assert(!lastRemaining(0, 3));
    assert(!lastRemaining(5, 0));
    assert(!lastRemaining(-1, 3));
    assert(lastRemaining(1, 997) == 0);
 
    for (std::int64_t n = 1;
         n <= 50;
         ++n) {
        assert(lastRemaining(n, 1) ==
               static_cast<std::uint64_t>(
                   n - 1));
    }
}

完整模型对拍可在n和m都不超过几十时使用vector或list模拟删除，再比较最终编号。不要用同一个递推公式写“参考实现”，否则两边可能复制同一偏移错误。

本章练习

本章回顾

1. 约瑟夫环从当前元素开始按1计数，首次删除下标是m减1对n取模。
2. 链表法保存真实圆圈，删除后必须从被删节点后继继续。
3. 删除后把后继重编号为0，子问题与原问题规则同构。
4. 新编号映回旧编号时加m取模，因此递推f(n,m)=(f(n-1,m)+m)%n。
5. 基例f(1,m)=0，可以从1个数字反推到规模n。
6. 作者链表法时间O(nm)、空间O(n)；递推法时间O(n)、空间O(1)。
7. 0基与1基、m等于1、n等于1、无效输入和大整数都必须明确契约。
8. 作者六组测试同时验证两种解法，4000、997的期望为1027。

名词解释