Leetcode----面试题62. 圆圈中最后剩下的数字

我想到的方法是模拟，看了一下数据范围肯定超时，想着肯定有数学解法，看了下题解果然是有的。今天又是菜的一天。

这是一个经典的约瑟夫环的问题，我们先看一下，题目所给数据的模拟过程。

可以看出下一轮的第一个数是当前这一轮所删除数字下一个数向前移动m次，所以我们可以通过反推推出剩下的最后一个数在第一轮时的位置，这个位置的下标即为这个数。

公式：(当前位置下标+m) % 上一轮数组长度

1.在倒数第二轮的位置为$(0+3)\%2=1$(0+3)%2=1
2.在倒数第三轮的位置为$(1+3)\%3=1$(1+3)%3=1
3.在倒竖第四轮的位置为$(1+3)\%4=0$(1+3)%4=0
4.在倒数第五轮的位置为$(0+3)\%5=3$(0+3)%5=3

所以3是最后一个剩下的数字。

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