如何在O(N)时间内找到约瑟夫环问题的最后K个幸存者？

你已经知道用O(N)时间可以找到约瑟夫环的最后1个幸存者，但需要找到最后K个（K<5）被移除的位置（即倒数第2、3、4个幸存者对应的移除顺序位置），同时希望保持O(N)时间复杂度，而非全量解法的O(N log N)。

你使用的cp-algorithms的O(N)代码如下：

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
      res = (res + k) % i;
    return res + 1;
}

解决思路：反向递推最后K个位置 #

原代码是正向递推最后1个幸存者的位置，要找最后K个，我们可以从只剩K个人的状态反向递推回初始n个人的状态。因为K是极小的常数（<5），这个过程能保持O(N)时间复杂度。

具体逻辑：

• 当环中只剩K个人时，这K个人就是最后剩下的K个幸存者，他们在当前环中的位置为0到K-1（0-based）。
• 每次把环的规模从m-1扩大到m（m从K+1到n），将m-1环中的每个位置映射回m环中的位置，映射公式为(pos + k) % m——这是正向约瑟夫递推的逆过程。
• 维护一个大小为K的数组，保存当前环中最后K个幸存者的位置，逐步递推到m=n即可得到初始环中的位置。

代码实现（支持任意K<5） #

以下代码返回最后K个被移除的位置（转换为1-based），数组最后一个元素是最后1个幸存者的位置，第一个元素是倒数第K个被移除的位置：

#include <vector>
using namespace std;

vector<int> josephus_last_k(int n, int k, int K) {
    vector<int> survivors(K);
    // 初始化：K人环中，最后K个幸存者的位置是0..K-1（0-based）
    for (int i = 0; i < K; ++i) {
        survivors[i] = i;
    }
    // 从K+1人环递推到n人环
    for (int m = K + 1; m <= n; ++m) {
        for (int& pos : survivors) {
            pos = (pos + k) % m;
        }
    }
    // 转换为1-based位置
    for (int& p : survivors) {
        p += 1;
    }
    return survivors;
}

复杂度验证 #

因为K是常数（最多4），外层循环执行O(N)次，内层循环每次执行O(K)次，总时间复杂度为O(N*K)=O(N)，完全符合你的要求。

示例验证 #

比如n=5，k=2，K=2：

• 实际移除顺序是2→4→1→5，最后幸存者是3，倒数第2个被移除的是1。
  调用josephus_last_k(5,2,2)会返回[1,3]，和实际结果一致。

内容的提问来源于stack exchange，提问作者Lithanium