我是靠谱客的博主 自然水池,这篇文章主要介绍环形数组删除问题,现在分享给大家,希望可以做个参考。

问题描述:

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
21
int 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; }
这种方法由于用到了链表,空间复杂度O(n),且在遍历n个元素时,每删除一个元素时需要m步,故时间复杂O(mn)。

另外一个思路是通过数学推导:

在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
8
int 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; }
此时时间复杂度O(N),空间复杂度常数。

最后

以上就是自然水池最近收集整理的关于环形数组删除问题的全部内容,更多相关环形数组删除问题内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(72)

评论列表共有 0 条评论

立即
投稿
返回
顶部