题意:
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
方法:
模拟
思路:模拟。
首先,初始化 vis[ ] 数组表示每个人的状态;
遍历环形数组,报到m的人修改vis[ ] 数组的状态;一直循环遍历,直到只剩一个人。最后,返回最后留下的人编号。
class Solution { public: int vis[10005]={0};//判断是否离开 int ysf(int n, int m) { int cnt=n,num=0; for(int i=1;i<=n;i++){//循环 if(vis[i]==0){ num++; if(num==m){//报到m的人离开 vis[i]=1; cnt--; if(cnt==1) break; num=0; } } if(i==n){//保证环形 i=0; } } for(int i=1;i<=n;i++){//返回最后留下的人编号 if(vis[i]==0){ return i; } } return 0; } };
时间复杂度:空间复杂度: