剑指offer 面试题45—圆圈中最后剩余的数字（约瑟夫环）

剑指offer 面试题45—圆圈中最后剩下的数字（约瑟夫环）

题目：

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

解法一：

list实现环形链表，每当迭代器扫描到链表末尾的时候，把跌倒器移到链表的头部。这样就相当于按照顺序在一个圆圈里遍历了。

解法二：

数学公式

f(n,m)表示n个数字的序列中最后剩下的数字，只需要得到n-1个数字的序列中最后剩下的数字。

当n=1时，序列中开始只有一个数字0，那么最后剩下的数字就是0.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

//O(nm)
int foo1(int n,int m)
{
	if(n<1||m<1)
		return -1;

	list<int> a;
	for(int i=0;i<n;i++)
		a.push_back(i);

	list<int>::iterator cur = a.begin();

	while(a.size()>1)
	{
		for(int i=1;i<m;i++)
		{
			cur++;
			if(cur==a.end())
				cur=a.begin();
		}

		list<int>::iterator next = ++cur;
		if(next==a.end())
			next=a.begin();

		--cur;
		a.erase(cur);
		cur=next;
	}

	return *(cur);
}

//O(n)
int foo2(int n,int m)  
{  
	if(n<1||m<1)
		return -1;

    vector<int> people;  
    for (int i=0;i<n;i++)  
    {  
        people.push_back(i);  
    }  
    int start = 0;  
    int tmp =0;  
    int out;  
    while (tmp < n)  
    {  
        out=(start-1+m)%people.size();  
		tmp++;
        people.erase(people.begin()+out);  
        start=out;       
    }  
	return people[start];	
}

//O(n)
int foo3(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;
}


void main()
{
	int n,m;
	cin>>n>>m;

	cout<<foo1(n,m)<<endl;
	cout<<foo2(n,m)<<endl;
	cout<<foo3(n,m)<<endl;
}