剑指offer64_圆圈中最后剩下的数字

圆圈中最后剩下的数字

0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。

求出这个圆圈里剩下的最后一个数字。

数据范围

1≤n,m≤4000

样例2

输入：n=5 , m=3输出：3

算法思路

这是一个经典的约瑟夫环问题(Josephus problem)的递归解法。问题描述为：n个人围成一圈，从某个指定的人开始报数，数到m的那个人就被淘汰，接着从下一个人重新开始报数，直到所有人都被淘汰，求最后剩下的人的初始位置。

递归思路：

1. 基本情况：当只有1个人时(n=1)，这个人是最后剩下的，返回0（表示初始位置是0）
2. 递归情况：对于n个人，我们首先计算n-1个人时的解，然后加上m（因为每次淘汰第m个人），最后对n取模（因为是环形结构）

• 时间复杂度：O(n)，因为需要递归n次
• 空间复杂度：O(n)，递归调用栈的深度为n

class Solution {
public:int lastRemaining(int n, int m) {// 基本情况：只有一个人时，他就是最后剩下的if(n == 1) return 0;// 递归计算n-1个人的解，然后加上m并对n取模return (lastRemaining(n - 1, m) + m) % n;}
};

实例演示

示例：n=5, m=3

1. lastRemaining(5,3) = (lastRemaining(4,3)+3)%5
2. lastRemaining(4,3) = (lastRemaining(3,3)+3)%4
3. lastRemaining(3,3) = (lastRemaining(2,3)+3)%3
4. lastRemaining(2,3) = (lastRemaining(1,3)+3)%2
5. lastRemaining(1,3) = 0 (基本情况)
6. 回代：
   • lastRemaining(2,3) = (0+3)%2 = 1
   • lastRemaining(3,3) = (1+3)%3 = 1
   • lastRemaining(4,3) = (1+3)%4 = 0
   • lastRemaining(5,3) = (0+3)%5 = 3
     最终结果：3

优化建议

这个递归解法虽然简洁，但当n很大时可能会导致栈溢出。可以改用迭代方法来优化空间复杂度：

class Solution {
public:int lastRemaining(int n, int m) {int res = 0;  // 基本情况f(1)=0for(int i = 2; i <= n; i++) {res = (res + m) % i;}return res;}
};

迭代版本的空间复杂度降为O(1)，更适合处理大规模输入。