62.圆圈中最后剩下的数字（简单）

考点：本题考查抽象建模能力

题目描述：

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
(1) 0 1 2 3 4 删除2
(2) 3 4 0 1 删除0
(3) 1 3 4 删除4
(4) 1 3 删除1
(5) 3 最后剩下3
这是著名的约瑟夫环问题

思路一：用环形链表模拟圆圈

创建一个共有n个节点的环形链表，然后每次在这个链表中删除第m个节点
使用一个list来模拟，并使用一个索引current指向删除的位置，当current的值为list的size，就让current回到头位置

import java.util.LinkedList;
import java.util.List;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1)
            return -1;
        List<Integer> list=new LinkedList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int current = -1;
        while(list.size()>1){
            for(int i=0;i<m;i++){
                current++;
                if(current==list.size())
                    current = 0;
            }
            list.remove(current);
            current--;
        }
        return list.get(0);
    }
}

上述代码中存在重复的遍历，每删除一个数字需要m步运算，共有n个数字，总的时间复杂度为O(mn)

思路二：分析每次被删数字的规律

f(n,m)表示每次在n个数字0,1，...，n-1中删除第m个数字最后剩下的数字
当n=1时，f(n,m)=0
当n>1时，f(n,m)=[f(n-1,m)]%n

import java.util.LinkedList;
import java.util.List;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1)
            return -1;
        int res = 0;
        for(int i=2;i<=n;i++){
            res = (res+m)%i;
        }
        return res;
    }
}

时间复杂度为O(n)