1、前言

题目描述

2、思路

如果采用模拟的方法，比如新建链表之类的会超时。

此问题是一个约瑟夫环问题，利用数学手段得到公式为：f(n,m)=[f(n−1,m)+m]%n。

约瑟夫环

每次杀掉一个人，从后面的人开始重新编号，会发现最后的一个人为0。如果从 n = 1 递推，就会发现上面的公式：

公式

3、代码

class Solution {


    public int lastRemaining(int n, int m) {
        int pos = 0;
        for(int i = 2; i <= n; i++){
            pos = (pos + m) % i;
        }
        return pos;
    }
}