考点：本题考查抽象建模能力
题目描述：
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)
