【2022-11-06 加练约瑟夫环】剑指 Offer 62. 圆圈中最后剩下的数字[Easy]
2022-11-06
1分钟阅读时长
加练：剑指 Offer 62. 圆圈中最后剩下的数字
难度：Easy
标签：递归 、 数学
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^51 <= m <= 10^6
方法一：递归
核心思想：f(10,3)的结果就可以转化为f(9,3)的表达,后面也是同理：
f(10,3)=(f(9,3)+3)%10
f(9,3)=(f(8,3)+3)%9
……
f(2,3)=(f(1,3)+3)%2
f(1,3)=0
代码
func lastRemaining(n int, m int) int {
if n == 1 {
return 0
}
return (lastRemaining(n-1, m) + m) % n
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
方法二：迭代
func lastRemaining(n int, m int) int {
ans := 0
for i := 1; i <= n; i++ {
ans = (ans + m) % i
}
return ans
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。