编程算法 - 圆圈中最后剩下的数字(循环链表) 代码(C++)

圆圈中最后剩下的数字(循环链表) 代码(C++)

?

?

题目: 0,1...,n-1这n个数字排成一个圆圈, 从数字0开始每次从这个圆圈里删除第m个数字.

求出这个圆圈里最后剩下的数字.

?

使用循环链表, 依次遍历删除, 时间复杂度O(mn), 空间复杂度O(n).

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.13
 *      Author: Spike
 */

#include 
  
   
#include 
   
     using namespace std; int LastRemaining (size_t n, size_t m) { if (n<1 || m<1) return -1; list
    
      numbers; for(size_t i=0; i
     
      ::iterator current = numbers.begin(); while (numbers.size() > 1) { for (size_t i=1; i
      
       ::iterator next = ++current; //指向下一个 if (next == numbers.end()) next = numbers.begin(); --current; numbers.erase(current); current = next; } return *(current); } int main(void) { int result = LastRemaining(5, 3); std::cout << result = << result << std::endl; return 0; } 
      
     
    
   
  

?

?

result = 3

?

?

?