admin 管理员组

文章数量: 887031

【C++代码】约瑟夫环问题：0,1,……,n

问题描述：0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

       

这是力扣上的一道题。我的思路：

  • ①首先想到的是用循环链表，每次向后遍历找到第m个节点，从链表中删除，再找下一个第m个节点再删除，直到链表中剩下一个节点。但是链表不支持随机访问，每次访问往后的第m个结点也是很费时的。
           
  • ②然后想到用数组，数组支持随机读取，可以直接通过下标访问下一个第m个节点，但删除一个元素后，移动剩下元素要耗费大量时间。
           
  • ③那有没有用数组但又不删除元素的方法呢。每删除一个数，就把这个元素值置为-1，每经过m个不为-1的数，就把这个数值置为-1，直到数组中只剩下一个不为-1的元素，这个元素值就是答案。（这种方法效率和链表比起来也差不多）
           
    第③种方法虽然有数组的随机访问速度，也不用删除元素，但数据量大的时候，运行到后面数组内有大量值为-1的元素，要进行多次循环判断，速度也很慢，提交后直接超时。官方给出的是数学方法，找出问题的递归公式，几行代码解决。
           
  • ④数学方法（递推公式为 f(N,M)=(f(N−1,M)+M)%N ），数学公式如何推出来的见博客约瑟夫环——公式法（递推公式）

       
       

附上代码：

第①中方法（使用链表）：

// 定义链表的节点
struct node{int val;node *next;node(int val_,node *next_=nullptr){val=val_;next=next_;}
};class Solution {
public:int LastRemaining_Solution(int n, int m){if(n<=0 || m<=0){return -1;}if(m==1){return n-1;}// 创建一个链表node* head=new node(0);node* pre=head;for(int i=1;i<n;++i){node* cur=new node(i);pre->next=cur;pre=cur;}pre->next=head;// 逐步删除int sy=n;int i=0;while(sy>1){while(i<m-2){head=head->next;++i;}head->next=head->next->next;head=head->next;i=0;--sy;}return head->val;} 
};

       
       

第③种方法（使用数组）：

class Solution {
public:int lastRemaining(int n, int m) {vector<int> sq(n);int i=0;for (auto &it : sq) {it = i;++i;}int num = n;     // 记录数组内剩余的不为-1的元素个数int index = 0;   while (num>1) {        int j = 0;while (j ==0 || j != m) {if (sq[index % n] != -1) {++j;}++index;    }sq[(index-1)%n] = -1;	// 将第m个不为-1的元素值置为-1--num;}for (auto it : sq) {if (it != -1) {i = it;break;}}return i;}
};

       
       

第④中方法（数学公式，效率最高）：

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

本文标签： C代码约瑟夫环问题0 1 N

版权声明：本文标题：【C++代码】约瑟夫环问题：0,1,……,n 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687418969h100424.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。