剑指offer62 圆圈中最后剩下的数字【约瑟夫问题】
题目描述
0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
示例 1:
1 | 输入: n = 5, m = 3 |
示例 2:
1 | 输入: n = 10, m = 17 |
限制:
1 <= n <= 10^5
1 <= m <= 10^6
解题思路
[约瑟夫问题]
方法一:数学+递归
递归方程
$$
f(n,m)=f(n-1,m)+m) % n
$$
代码实现
1 | public int lastRemaining(int n, int m) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) #递归栈
方法二:数学+迭代
使用的迭代的方法优化递归。
代码实现
1 | public int lastRemaining2(int n, int m) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
问题
本题是找出最后剩下的那个数,如何找到第n个淘汰的数呢?如何得出每一轮淘汰的数呢?
资料
剑指offer62 圆圈中最后剩下的数字【约瑟夫问题】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.