n个人围成一圈，第一个人从1开始报数，报m的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。

方法一：模拟+ 队列

  1. int findTheWinner(int n, int k) {
  2.     queue<int> que;
  3.     for (int i = 1; i <= n; i++) {
  4.         que.emplace(i);
  5.     }
  7.     while (que.size() > 1) {
  8.         for (int i = 0; i < k - 1; i++) {
  9.             que.emplace(que.front());
  10.             que.pop();
  11.         }
  12.         que.pop();
  13.     }
  14.     return que.front();
  15. }
  16. // 时间复杂度O(nk), 空间复杂度O(n)

方法二：约瑟夫环

解题思路：只关心最终活着那个人的序号变化

递归解法

每次往同一方向，以固定步长 k 进行消数。由于下一次操作的发起点为消除位置的下一个点（即前后两次操作发起点在原序列下标中相差 k），同时问题规模会从 n 变为 n - 1，因此原问题答案等价于 findTheWinner(n - 1, k) + k。
一些细节，由于编号从 1开始，在返回答案时我们需要将结果为 0 的值映射回编号 n。

  1. int findTheWinner(int n, int k) {
  2.     if (n == 1) {
  3.         return 1;
  4.     }
  5.     int ans = (findTheWinner(n - 1, k) + k) % n;
  6.     return (ans == 0) ? n : ans;
  7. }
  8. // 时间复杂度O(n), 空间复杂度O(n)

迭代解法

  1. int findTheWinner(int n, int k) {
  2.     int ans = 0; // 最终活下来那个人的初始位置
  3.     for(int i = 2; i <= n; i++){
  4.         ans = (ans + k) % i;  // 每次循环右移
  5.     }
  6.     return ans + 1;
  7. }
  9. // 时间复杂度O(n), 空间复杂度O(1)

解题思考过程

  1. 问题转换

下面这个例子是N=8 m=3的例子
我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关系最后剩下来这个人的索引号的变化情况即可。
image.png

从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号

  • 第一次C被杀掉，人数变成7，D作为开头，（最终活下来的G的编号从6变成3）
  • 第二次F被杀掉，人数变成6，G作为开头，（最终活下来的G的编号从3变成0）
  • 第三次A被杀掉，人数变成5，B作为开头，（最终活下来的G的编号从0变成3）
  • 以此类推，当只剩一个人时，他的编号必定为0！（重点！）
  1. 最终活着的人编号的反推

现在我们知道了G的索引号的变化过程，那么我们反推一下
从N = 7 到N = 8 的过程
如何才能将N = 7 的排列变回到N = 8 呢？
我们先把被杀掉的C补充回来，然后右移m个人，发现溢出了，再把溢出的补充在最前面
神奇了 经过这个操作就恢复了N = 8 的排列了！
image.png
因此我们可以推出递推公式f(8,3) = [f(7, 3) + 3]% 8
进行推广泛化，即f(n,m)=[f(n−1,m)+m]%n
换个说法：
我们将上述问题建模为函数 f(n, m)，该函数的返回值为最终留下的元素的序号。
首先，长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n - 1 的序列。那么，我们可以递归地求解 f(n - 1, m)，就可以知道对于剩下的 n - 1 个元素，最终会留下第几个元素，我们设答案为 x = f(n - 1, m)。
由于我们删除了第 m % n 个元素，将序列的长度变为 n - 1。当我们知道了 f(n - 1, m) 对应的答案 x 之后，我们也就可以知道，长度为 n 的序列最后一个删除的元素，应当是从 m % n 开始数的第 x 个元素。因此有 f(n, m) = (m % n + x) % n = (m + x) % n。

  1. 递推公式的导出

再把n=1这个最初的情况加上，就得到递推公式
image.png