剑指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();
      	}
      }
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/97983965