leedcode:圆圈中最后剩下的数字（约瑟夫环问题）

3.30日：圆圈中最后剩下的数字(约瑟夫环问题)

0,1,…,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

分析：给出递推公式f(N,M)=(f(N?1,M)+M)%N

• *f(N,M)*表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
• *f(N-1,M)*表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

上图表格每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

• f(1,3)：只有1个人了，那个人就是获胜者，他的下标位置是0
• f(2,3)=(f(1,3)+3)%2=3%2=1：在有2个人的时候，胜利者的下标位置为1
• f(3,3)=(f(2,3)+3)%3=4%3=1：在有3个人的时候，胜利者的下标位置为1
• …
• f(11,3)=6

第一种：模拟链表O(n²)

N个人看作是N个链表节点，节点1指向节点2，节点2指向节点3，……，节点N-1指向节点N，节点N指向节点1，这样就形成了一个环。然后从节点1开始1、2、3……往下报数，每报到M，就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

但是要模拟整个游戏过程，时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。果断放弃！

第二种：公式法O(n)

#python解法
class Solution:def lastRemaining(self,n,m):f = 0for i in range(2,n + 1):f = (m + f) % ireturn f

//java解法
class Solution{
    public int lastRemaining(int n,int m){
    int ans = 0;//最后一轮剩下2个人，所以从2开始反推for (int i = 2;i <= n;i++){
    ans = (ans + m) % i;}return ans;}
}