数学
如下表所示,每轮去掉的数的后一个数重新设置为0开头,重新排序0,1,2,...,
然后逆向找对应的idx
n | m = 2 | f(n,m) |
---|---|---|
5 | 0,√,2,3,4 | f(5,2)=(f4,2)+2)%5=2 |
4 | 3,x,0,√,2 | f(4,2)=(f(3,2)+2)%4=0 |
3 | √,x,2,x,0 | f(3,2)=(f(2,2)+2)%3=2 |
2 | x,x,0,x,√ | f(2,2)=(f(1,2)+2)%2=0 |
1 | x,x,0,x,x | f(1,2)=0 |
√表示每轮需要去掉的数,x表示每轮不存在的数
时间复杂度:
空间复杂度:
class Solution { public: /** * * @param n int整型 * @param m int整型 * @return int整型 */ int ysf(int n, int m) { // write code here int i = 1; int idx = 0; while(i <= n){ idx = (idx + m) % i; i ++; } return idx + 1; } };