剑指offer之圆圈最后剩下的数

1 问题 

求圆圈最后剩下的数，比如数组0, 1, 2 ,3 ,4围城一个环，我们每次去掉第三个数字，删除的前4个数字依次是2, 0, 4, 1，最后剩下的数字是3

                  0

         4               1

           3           2

2 思路

我们用list,我们要支持环就这样,如果发现当前指针指向是尾巴的时候，我们把它指向链表的开始。

3 代码实现

#include <iostream>
#include <list>

using namespace std;

int getIndex(int n, int m)
{
if (n < 1 || m < 1)
{
return -1;
}
list<int> numbers;
for (int i = 0; i < n; ++i)
{
numbers.push_back(i);
}
list<int>::iterator current = numbers.begin();
while(numbers.size() > 1)
        {
for(int i = 1; i < m; ++i)
{
current++;
//指针向右移动的时候需要判断是否到了数组尾巴
if (current == numbers.end())
{
current = numbers.begin();
}
}
//指针向右移动的时候需要判断是否到了数组尾巴
list<int>::iterator next = ++current;
if (next == numbers.end())
{
next = numbers.begin();
}
current--;
                //删除指定的元素
numbers.erase(current);
current = next;
}
return *(current);
}

int main()
{
int a[] = {0, 1, 2, 3, 4};
int index = getIndex(5, 3);
if (-1 != index)
        {
std::cout << a[index] << std::endl;
}
return 0;
}

 

4 运行结果

3

 

5 总结

如果我们需要环的数据结构，我么可以使用list数据结构，然后当指针指向尾巴的时候我们指向头。

list<int> numbers;
for (int i = 0; i < n; ++i)
{
numbers.push_back(i);
}
list<int>::iterator current = numbers.begin();
for (int i = 1; i < m; ++i)
{
++current;
if (current == numbers.end())
{
current = numbers.begin();
}
}