博客

力扣_圆圈中最后剩下的数字

解法1：

假设当前删除的位置是idx，下一个删除的数字的位置是idx+m 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是idx+m−1。由于数到末尾会从头继续数，所以最后取模一下，就是(idx+m−1)(modn)。

public class Num62_圆圈中最后剩下的数字 {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }

}