面试题62. 圆圈中最后剩下的数字(简单)

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

思路1：

第一反应就是使用数组或者链表进行模拟，但是复杂度太高O（mn）

思路2：

约瑟夫环问题递归解法的一点理解

约瑟夫环之二(用递归的思想解决Josephus问题)

约瑟夫环问题，这里参考题中一个解答

约瑟夫问题比较难想的点有两个：

当数到最后一个结点不足m个时，需要跳到第一个结点继续数。
每轮都是上一轮被删结点的下一个结点开始数 m 个。
第一点比较好解决，可以通过取余来完成。
第二点的解决方案是：将删除结点的后继作为下一轮的第一个结点，后续结点依次排列。这样每轮都是从首结点开始数 m 个了。

通过观察上图中的结点对应关系可以发现：设下一轮的最后结点编号为 p，那么当前一轮的最后结点为从被删除结点向后偏移 p+1 处的结点 ！！！
换一个更好用代码实现的描述方式：从被删除结点的下一个结点偏移 p 处的结点，编号为 ((m%n) + p)%n
一个递推式子已经呼之欲出了！！！OMG ！！！
设函数 f(n,m) 输出最后结点的编号，结点编号从 0 开始，n 为结点个数，m 为删除步长。
$$
f(n, m)=\left{\begin{array}{cl}
0, & n=1 \
((m % n)+f(n-1, m)) % n, & n>1
\end{array}\right.
$$

n = 1 时显然成立。接下来分析一下 n > 1 时式子：

作者：Time-Limit
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/chi-jing-stsu-degd-degtsu-tu-jie-yue-se-fu-huan-hu/

回看记录200726

约瑟夫环需要补习

代码1：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int lastRemaining(int n, int m) {
        if(n==1)
		    return 0;
        int res=0;
        for(int i=2;i!=n+1;i++){
            res = (m+res)%i;
        }
        return res;
    }
}