口试经典（23）-圆圈中剩下的最后数字

面试经典（23）--圆圈中剩下的最后数字

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

解法1：数组模拟

使用数组来模拟的话空间复杂度和时间复杂度都会比较高，不过为了锻炼下逻辑思维，我们先使用数组。将长度为n的数组初始化0，变量count表示当前退出的人数，只要count=n-1就可以完成任务。t表示报数计数，当t=m时就将数组当前i位置元素置1，表示i位置元素退出，遍历数组遇到元素为1的位置直接跳过。先处理要特殊处理的情况，然后再处理正常逻辑部分。

代码如下：

//n个人从0--n-1编号，从第一个人报数，数到m的退出.
int FindLastOne(int n,int m)
{
	if(n<1 || m<1)
		return -1;
	int *data=new int[n];
	memset(data,0,n*sizeof(int));
	int t=0,count=0,i=0;
	while(count<n-1)
	{
		if(data[i]==0)
			t++;
		if(t==m)
		{
			t=0;
			data[i]=1;
			++count;
		}
		i++;
		if(i==n)
			i=0;
	}
	int res;
	for(i=0;i<n;i++)
		if(data[i]==0)
			res=i;
	delete[] data;
	return res;
}

解法2：数学魅力

int lastRemain(int n,int m)
{
	if(n<1 || m<1)
		return -1;
	int last=0;
	for(int i=2;i<=n;i++)
		last=(last+m)%i;
	return last;
}