剑指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