题目描述

0始排位下标，报数自1开始，n个人报m个数的经典约瑟夫环问题。

样例

输入：n=5 , m=3

输出：3

参考文献

今日头条2018春招研发岗笔试 by yxc
1455. 招聘

算法1

(递归版) $O(n)$

0始下标
f(n, m) = (f(n - 1, m) + m) % n

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int lastRemaining(int n, int m){
        if(n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};

py3 代码(会爆栈)

class Solution(object):
    def lastRemaining(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        return 0 if n == 1 else (self.lastRemaining(n - 1, m) + m) % n

算法2

(迭代版) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int lastRemaining(int n, int m){
        int f = 0;
        for(int i = 2; i <= n; i ++){
            f += m;
            if (f >= i) f %= i;
        }
        return f;
    }
};

py3 代码

class Solution(object):
    def lastRemaining(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        f = 0
        for i in range(2, n + 1):
            f += m
            if f >= i: f %= i
        return f