题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    //约瑟夫问题 排队枪毙问题
    int lastRemaining(int n, int m){ // lastRemaining计算的是最新的编号 但需要返回旧编号
        if(n == 1) return 0; // 当前新编号的第0位,具体是旧编号的第几位,需要递归出栈
        return (lastRemaining(n - 1 , m) + m) % n; // 旧编号 = （新编号 + m）% n
    }
};

#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        list<int> nums;
        for(int i = 0 ; i < n ; i++) nums.push_back(i);

        auto iter = nums.begin();

        while(nums.size() != 1){
            for(int i = 0 ; i < m - 1 ; i++){
                iter++;
                // 如果指向最后一个元素的下一位了，让它重新指向头个元素
                if(iter == nums.end()) iter = nums.begin(); // nums.end()指向list最后一个元素下一位
            }
            iter = nums.erase(iter); // 删除第m个元素 并返回指向下一个元素的迭代器

            if(iter == nums.end()) iter = nums.begin();
        }
        return nums.front();

    }
};