问题描述:
n个数字组成的序列(0,1,2...,n-1),组成一个圆圈,从数字0开始,每次删除第m个数字,当当前这个数字删除后,从这个数字下一个数字开始同样开始删除第m个数字,直到这个圆圈只剩一个数字为止。
这是面试笔试常考的类型,最常见的思路:
一链表实现,为了简单,这里不再单独构造链表结构,直接引入C++ STL的list,只不过这里需要环形链表,所以在list遍历到end位置时将迭代器位置赋值为begin,算法思路很直白,每m-1个删除一个数字:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21int LastRemain1(int n,int m){ if(n<1||m<1)return -1; list<int>intergers; for(int i=0;i<n;i++) intergers.push_back(i); list<int>::iterator it=intergers.begin(); while(intergers.size()>1){ for(int j=1;j<m;j++) { it++; if(it==intergers.end())it=intergers.begin(); }//找到删除的位置 list<int>::iterator it1=(++it); if(it1==intergers.end())it1=intergers.begin(); it--; intergers.erase(it); it=it1; } return *it; }
另外一个思路是通过数学推导:
在n个数字中,第一个被删除的数字k=(m-1)%n,删除后剩下的n-1个数字为,0,1,...,k-1,k+1,k+2,...,n-1,若转换为0-xx的形式,则映射关系如下:
X P
k+1----------------------------------------0
k+2----------------------------------------1
... ---------------------------------------...
n-1-----------------------------------------n-k
0 -----------------------------------------n-k+1
1 -----------------------------------------n-k+2
...--------------------------------------------...
k-1------------------------------------------n-2
即P=(x-k-1)%n,由此可以得x=(p+k+1)%n。
另外:设最初n个数字中最后一个数字可以是关于m和n的方程f(n,m),其实也是删除k以后n-1个数字的最后一个数字f''(n-1,m),将是删除k以后n-1个数字经过上述映射转换为原始的n个数字类型(即从0开始)则f''(n-1,m)=(f(n-1,m)+k+1)%n则有f(n,m)=[f(n-1,m)+m]%m
1
2
3
4
5
6
7
8int LastRemain2(int n,int m){ if(n<1||m<1)return -1; if(n==1)return 0; int last=0; for(int i=2;i<=n;i++) last=(last+m)%i; return last; }
最后
以上就是自然水池最近收集整理的关于环形数组删除问题的全部内容,更多相关环形数组删除问题内容请搜索靠谱客的其他文章。
发表评论 取消回复