AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 82. 圆圈中最后剩下的数字    原题链接    简单

作者: 作者的头像   cornerCao ,  2019-01-17 16:38:41 ,  所有人可见 ,  阅读 6290


38


20

算法1

(链表模拟) $O(mn)$

本题就是有名的约瑟夫环问题。我们可以环形列表来模拟,每次从这个列表中删除第m个元素,一直到列表最后剩下一个元素为止。

考虑用STL中std::list来模拟这个环形列表,由于list并不是一个环形的结构,因此每次跌代器扫描到列表末尾的时候,要记得把跌代器移到列表的头部。这样就是按照一个圆圈的顺序来遍历这个列表了。

由于我们需要一个有n个结点的环形列表来模拟这个删除的过程,因此内存开销为O(n)。而且这种方法每删除一个数字需要m步运算,总共有n个数字,因此总的时间复杂度是O(mn)。

时间复杂度分析:$O(mn)$

C++ 代码

#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 it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1){
            while (k--){
                it++;
                if (it == nums.end()) it = nums.begin();//别迭代器移到开头实现模拟环形列表
            }
            it = nums.erase(it);//删除第m个元素
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();
    }
};

算法2

(推导递推公式) $O(n)$

在《剑指offer》上对该问题从数学上分析出了一些规律。首先定义最初的n个数字(0,1,…,n-1)中最后剩下的数字是关于n和m的方程为f(n,m)。

在这n个数字中,第一个被删除的数字是(m-1)%n,为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1,并且下一个开始计数的数字是k+1。相当于在剩下的序列中,k+1排到最前面,从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样(最初的序列是从0开始的连续序列),因此该函数不同于前面函数,记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m),所以f(n,m)=f’(n-1,m)。

接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射,映射的结果是形成一个从0到n-2的序列:

k+1    ->    0
k+2    ->    1
…
n-1    ->    n-k-2
0   ->    n-k-1
…
k-1   ->   n-2

把映射定义为p,则p(x)= (x-k-1)%n,即如果映射前的数字是x,则映射后的数字是(x-k-1)%n。对应的逆映射是p-1(x)=(x+k+1)%n。

由于映射之后的序列和最初的序列有同样的形式,都是从0开始的连续序列,因此仍然可以用函数f来表示,记为f(n-1,m)。根据我们的映射规则,映射之前的序列最后剩下的数字f’(n-1,m)= p-1 [f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=(m-1)%n代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。

经过上面复杂的分析,我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下的数字,只需要得到n-1个数字的序列的最后剩下的数字,并可以依此类推。当n=1时,也就是序列中开始只有一个数字0,那么很显然最后剩下的数字就是0。因此有递推公式:

当n=1时,f(n, m) = 0
当n>1时,f(n, m) = [f(n-1, m) +m] % n

因此就可以递归求解,复杂度为$O(n)$。

时间复杂度分析:$O(n)$

C++ 代码

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

11 评论


用户头像
胖嘟嘟的大瑜   2022-09-07 11:41      4    踩      回复

list_name.end()不是指向list最后的元素,是最后的下一个,也就是空(当时困扰我很久,希望后来人不要踩坑)

用户头像
极尽智慧放飞梦想   2023-08-03 14:28         踩      回复

好的感谢


用户头像
Njr   2020-08-13 17:13      1    踩      回复

剑指原封不动搬下来,中间也没说清楚


用户头像
数学能考一百分   2025-04-11 14:54 · 河南         踩      回复

class Solution {
public:
int lastRemaining(int n, int m){
queue[HTML_REMOVED] q1;
for(int i = 0;i < n;i++) {
q1.push(i);
}
while(q1.size() > 1) {
int c = m - 1;
while(c–) {
q1.push(q1.front());
q1.pop();
}
q1.pop();
}
return q1.front();
}
};


用户头像
KillLemon   2023-09-29 19:45         踩      回复

为什么这样写会出错

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

       while (l.size() > 1) {
           for (int i = 0; i < m - 1; i ++) {
               if (it == l.end()) it = l.begin();
               it ++;
           }

           it = l.erase(it);
           if (it == l.end()) it = l.begin();
       }

       return l.front();
    }
};
用户头像
KillLemon   2023-09-29 19:51         踩      回复

忽然明白了,因为it++可能为l.end(),这样erase end会出问题!


用户头像
lemoba   2021-01-19 09:04         踩      回复

n - 2


用户头像
一念花开   2020-06-06 17:25         踩      回复

小姐姐的算法水平达到啥层次了?


用户头像
晓玲   2020-05-18 12:31         踩      回复

赞,学习了!!


用户头像
Krysta1ove   2020-05-17 09:56         踩      回复

看过解释最清楚的证明了。。


用户头像
周小伦   2020-03-17 22:35         踩      回复

小姐姐题解写的真棒~


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息