题意:
编号为 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;
}
};
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号