数据结构学习 jz62 圆圈中最后剩下的数字

关键词：数学?约瑟夫环问题

这个题如果用模拟方法是一定会超时的。

只能用约瑟夫环问题来解决。?

题目：破冰游戏

?思路：

关键是从我们需要的数x倒推回去。最后一个成员，它的索引一定为0，从索引0倒退回去。

请看这位大姐姐的答案。

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        int res=0;
        for(int i=2;i<=num;i++)
        {
            res=(res+target)%i;
        }
        return res;
    }
};