剑指offer：圆圈中最后剩下的数字（约瑟夫环）

本文主要是介绍剑指offer：圆圈中最后剩下的数字（约瑟夫环），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

思路：

方法1：用环形链表模拟圆圈，每次到第m个节点删除对应节点，知道最后剩下一个数字。比较费时，每删除一个元素需要m步运算，一共n个元素，所以时间复杂度O(mn)，空间复杂度为O(n)。

实现思路a：用模板库的std:list来模拟环形链表，因为链表可以方便的删除节点，但是因为不是环，当迭代器走到尾部时也要手动将其置为头部。

注意list的使用：

1）定义：list<int> num;

2）迭代器的定义： list<int>::iterator curr=num.begin();

3）vector容器的迭代器可以加1减1，也可以++，--，但是list容器的迭代器不能加1减1，只能++，--。原因是list容器不支持像vector容器那样的快速随机访问，只能依次访问每个元素，所以不支持加减等数术运算。

4）用迭代器访问元素需要解引用：*iter。

5）用erase删除元素。

对于关联容器（如map，set，multimap，multiset），删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前的iterator即可。

对于序列式容器（如vector，deque，list等），删除当前的iterator会使后面所有元素的iterator都失效。这是因为vector，deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。没有失效啊???

不过erase方法可以返回下一个有效的iterator。所以下面的代码还有一种更简洁的写法可以不用next迭代器。

 

实现思路b：用数组实现，因为数组访问元素很方便，而且下标就是对应的数字。首先数组删除节点不方便，所以直接将要删除的节点设为-1。其次当遍历到i==n时,要重新将i设为0，从头开始。先申请一个长度为n的动态数组，然后把0~n的值放进去，用count记录每一轮的计数，每次count=m时，将此时i处数字设为-1，之后每次遍历到-1的点直接跳过，用sum记录数组中不为-1的数，当sum==0时代表所有数字都已删除，此时的下标对应最后一个被删除的位置，也是最后剩下的数字。

方法2：分析每次删除的数字规律，时间复杂度O(n)，空间复杂度为O(1)。

设f(n,m)表示从长度为n的序列中删除第m个数字最后剩下的数字，则有递推公式：

分析过程：定义一个函数表示从长度为n的序列中每次删除第m个数字最后剩下的数字，删除的第一个元素是，删除这个元素之后的序列是L1：0,1,2,...,k-1,k+1,...,n-2，并且下一次从k+1开始计数，重排序列为P2：k+1,...,n-2,0,1,2,...,k-1。用另一个函数表示从重排后长度为n-1的序列P2中每次删除第m个数字最后剩下的数字（下标不一样了，所以函数关系变了），由于都是接着第一步之后进行完剩下的删除，所以两个操作最后剩下的数字都一样，即。下面建立一个P2到顺序下标序列P3:0,1,2,...,n-2的映射，这个映射关系是，由于映射后的序列是从0开始排序，也是从0开始删除，只是序列长度为n-1，所以最后剩下的数字可以用表示。可知有，把k代入可得到。

参考代码：

在线测试

https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

AC代码

方法1思路a：list

class Solution {
public:int LastRemaining_Solution(int n, int m){if(n<=0||m<=0)return -1;list<int> num;for(int i=0;i<n;i++){num.push_back(i);}list<int>::iterator curr=num.begin();//直到最后只剩下一个数字while(num.size()>1){//j从1开始for(int j=1;j<m;j++){curr++;if(curr==num.end())curr=num.begin();}//结束循环时curr指向要删除的位置/*写法1curr++;list<int>::iterator next=curr;//保存下一个起始位置if(next==num.end())next=num.begin();curr--;num.erase(curr);//删除当前位置curr=next;//从下一个位置开始重新计数*///写法2，更简洁curr=num.erase(curr);//erase删除当前的返回下一个迭代器if(curr==num.end())curr=num.begin();}return *(curr);//迭代器解引用}
};

方法1思路b：数组

class Solution {
public:int LastRemaining_Solution(int n, int m){if(n<=0||m<=0)return -1;int *num=new int[n];for(int i=0;i<n;i++){num[i]=i;}int count=0;//计数变量count初始化int sum=n;//剩下的节点数int index=-1;while(sum){index++;//如果还有节点剩下，index往后走if(index==n)//如果往后走到尾了，再回到头部index=0;if(num[index]==-1)//如果往后走了发现节点已删除，直接跳过，继续index++，不对count和sum以及数组中元素做任何操作continue;count++;//如果节点有效，count加1if(count==m)//已经是第m个点{num[index]=-1;//删除count=0;//count清零sum--;//剩下的节点少1}}return index;}
};

方法2：

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

 

这篇关于剑指offer：圆圈中最后剩下的数字（约瑟夫环）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---