剑指Offer 62 圆圈中最后剩下的数字
1. 题目概览
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
- 1 <= n <= 10^5
- 1 <= m <= 10^6
2. 解题思路
2.1 方法一：约瑟夫环
以下推导来自维基百科
我们将明确解出$k=2$时的问题。对于$k\ne2$的情况，我们在下面给出一个一般的解法。 设$f(n)$为一开始有$n$个人时，生还者的位置（注意：最终的生还者只有一个）。走了一圈后，所有偶数号码的人被杀。再走第二圈，则新的第二、第四、......个人被杀，等等；就像没有第一圈一样。如果一开始有偶数个人，则第二圈时位置为$x$的人一开始在第$2x-1$个位置。因此位置为$2f(n)-1$。这便给出了一下的递推公式： $$f(2n)=2f(n)-1$$
如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样的，再走第二圈是，新的第二、第四、......个人被杀，等等。在这种情况下，位置为$x$的人原先的位置是$2x+1$。这便给出了一下的地推公式： $$ f(2n+1)=2f(n)+1 $$
如果我们把$n$和$f(n)$的值列成表，我们可以看出一个规律：
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f(n)$ | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
从中可以看出，$f(n)$是一个递增的奇数数列，每当n是2的幂时，便重新从$f(n)=1$开始。因此，如果我们选择m和l，使得$n=2^{m}+l$且$0\leq l<2^{m}$，那么$f(n)=2\cdot l+1$。注意：$2^m$是不超过n的最大幂，l是留下的量。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。
定理： 如果$n=2^{m}+l$且$0\leq l<2^{m}$，则$f(n)=2l+1$。
证明： 对$n$应用数学归纳法。$n=1$的情况显然成立。我们分别考虑$n$是偶数和$n$是奇数的情况。
如果$n$是偶数，则我们选择$l{1}$和$m{1}$，使得$n/2=2^{{m{1}}}+l{1}$，且$0\leq l{1}<2^{{m{1}}}$。注意$l{1}=l/2$。我们有$f(n)=2f(n/2)-1=2((2l{1})+1)-1=2l+1$，其中第二个等式从归纳假设推出。
如果$n$是奇数，则我们选择$l{1}$和$m{1}$，使得$(n-1)/2=2^{{m{1}}}+l{1}$，且$0\leq l{1}<2^{{m{1}}}$。注意$l{1}=(l-1)/2$。我们有$f(n)=2f((n-1)/2)+1=2((2l{1})+1)+1=2l+1$，其中第二个等式从归纳假设推出。证毕。
答案的最漂亮的形式，与$n$的二进制表示有关：把$n$的第一位移动到最后，便得到$f(n)$。如果$n$的二进制表示为$n=b{0}b{1}b{2}b{3}\dots b{m}$，则$f(n)=b{1}b{2}b{3}\dots b{m}b{0}$。这可以通过把$n$表示为$2^{m}+l$来证明。
一般情况下，考虑生还者的号码从$n-1$到$n$的变化, 我们可以得到以下的递推公式(编号从0开始)：
$$ f(n,k)=(f(n-1,k)+k)\mod{n},f(1,k)=0 $$
这种方法的运行时间是$O(n)$。
非递归版
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
for (int i = 2; i <= 2; i++) {
ans = (ans + m) % i;
}
return s;
}
}
递归版
class Solution {
public int lastRemaining(int n, int m) {
return n > 1 ? (lastRemaining(n - 1, m) + k) % n : 0;
}
}
对于$k<n$，可以将上述方法推广，将杀掉第$k,2k,......,\lfloor n/k\rfloor$个人视为一个步骤，然后把号码改变，可得到如下递推公式，运行时间$O(k \log{n})$
$$ f(n,j)= \begin{cases} 0 & \rm{if}\ n = 1 \ (f(n-1,k)+k)\mod{n} & \rm{if}\ 1<n<k \ \lfloor \frac{k((f(n^{'},k)-n\mod{k})\mod{n^{'}})}{k-1} \rfloor \rm\ {where}\ n^{'}=n-\lfloor \frac{n}{k}\rfloor & \rm{if}\ k\le n \end{cases} $$
class Solution {
public int lastRemaining(int n, int m) {
if (m == 1) return n - 1;
int ans = 0;
for (int i = 2; i <= n; ) {
if (and + k >= i) {
ans = (ans + k) % i;
i++;
continue;
}
int step = (i - 1 - ans - 1) / (k - 1);
if (i + step > n) {
ans += (n - (i - 1)) * k;
break;
}
i += step;
ans += step * k;
}
return ans;
}
}