【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!...
题目链接
LeetCode 面试题62. 圆圈中最后剩下的数字题目描述
这 个数字排成一个圆圈,从数字 开始,每次从这个圆圈里删除第 个数字。求出这个圆圈里剩下的最后一个数字。
例如, 这 个数字组成一个圆圈,从数字 开始每次删除第 个数字,则删除的前 个数字依次是 ,因此最后剩下的数字是 。
示例1
输入:
n = 5, m = 3
输出:
3
示例2
输入:
n = 10, m = 17
输出:
2
说明:
题解
循环链表
用一个循环链表按顺序存储 到 中的数,然后每 个数删除掉链表中的一个结点,最后剩下的数就是答案了。
这种方法时间复杂度是 ,显然太高了,所以这里也不会给大家实现代码。
递推法
首先 个人的编号依次是 ,然后踢掉了编号为 的人,这时候剩下的人编号为 。
下一个踢掉的人就要从 开始数了,所以我们把剩下的人编号从 开始重新排个序,变成 。这样编号又变成连续的了,而问题规模缩减成了 个人。
剩下的这 个人的编号我们做一下映射,映射成 ,这样就能递推下去求解了。映射的公式就是,映射后的编号为 ,那么映射之前的编号就是 。
也就是说,如果我们求出了 个人最后剩下的人编号 ,那么 个人最后剩下的人编号就是 。
用 表示 个人最后剩下的人编号,那么就有:
这样的话时间复杂度就降到了 。
对于本题这个方法已经够用了,但是如果 非常大,比如 ,但是 不是很大,比如 ,那么这时候这种方法就会超时了。具体的题目请自行百度 HDU 3089 。
递推法加速
注意观察上面的递推式 ,如果 很小,而 很大的话,递推到后面要加很多次 才会对 求余。所以我们可以直接一下子加很多次 ,然后再求余,这样就能加速了。
加了 次 之后,递推式变成了:
假设加了 次 之后才产生了取余,那么就有 ,即 。所以每次都可以加 个 ,代码实现时用下取整,也就是 。
此外还需要注意,如果发现 ,也就是后面都不需要取余了,那么就直接一步加到底,退出循环得到答案。
这个方法时间复杂度不是很好分析,但应该也是对数级别的。
数学法
这个方法在我之前的文章中已经讲过了:
知乎高赞回答也整理过了一遍:
大致思想也是重新编号,做编号映射,但是和上面递推法不同的是复杂度降到了对数级别。
这里就不详细讲了,大家可以去看上面的文章,这里直接给出伪代码:
D = 1
while D <= (m-1)n:
D = k
ans = mn+1-D
其中 。
不过这个这里的编号是 到 ,所以最后答案要减去 。
这种方法将时间复杂度降到了 ,用对数换底公式后得到 。
可以看出,这种方法适用于 特别大,但是 特别小的情况。否则的话如果 很大,分母会非常小,导致复杂度非常高。
代码
递推法(c++)
class Solution {
public:
int lastRemaining(int n, int m) {
int last = 0;
for (int i = 2; i <= n; ++i) {
(last += m) %= i;
}
return last;
}
};
递推法加速(c++)
class Solution {
public:
int lastRemaining(int n, int m) {
if (m == 1) return n-1;
int last = 0, t = 1;
for (int i = 2; i <= n; i+=t) {
t = (i-last+m-3) / (m-1);
if (i+t-1 > n) {
last += (n-i+1)*m;
break;
}
(last += t*m) %= (i+t-1);
}
return last;
}
};
数学法(c++)
class Solution {
public:
int lastRemaining(int n, int m) {
long D = 1, end = (long)n*(m-1);
while (D <= end) {
D = (m*D+m-2) / (m-1);
}
return (long)n*m-D;
}
};
参考资料
[1]
LeetCode 面试题62. 圆圈中最后剩下的数字: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[2]
韦阳的博客:具体数学-第8课(取整进阶): https://godweiyang.com/2018/04/16/concrete-math-8/
[3]
知乎专栏:具体数学-第8课(取整进阶): https://zhuanlan.zhihu.com/p/35820332
[4]
世界上有哪些代码量很少,但很牛逼很经典的算法或项目案例?: https://www.zhihu.com/question/358255792/answer/974983270
公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。