圆圈中最后剩下的数字（不太理解方法2）

本文主要是介绍圆圈中最后剩下的数字（不太理解方法2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：0,1,…,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。（约瑟夫环问题）

方法1：用环形链表（std::list）模拟，每当迭代器（Iterator）扫描到链表末尾的时候，把迭代器移到链表的头部，这就相当于按照顺序在一个圆圈里遍历。时间复杂度O(mn)，空间复杂度O(n)。

int LastRemaining(unsigned int n, unsigned int m){if (n < 1 || m < 1){return -1;}unsigned int i = 0;list<int> numbers;for (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);
}

方法2：使用递推关系。时间复杂度O(n)，空间复杂度O(1)

$$\begin{equation} \notag f(n,m)= \left\{ \begin{aligned} &0,&if\;n &= 1,\\ &[f(n-1,m)+m]\%n,&if\;n&>1. \end{aligned} \right. \end{equation}$$

int LastRemaining(unsigned int n, unsigned 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;
}

测试用例：

• 功能测试（输入的m小于n，比如从最初有5个数字的圆圈删除每次第2、3个数字；输入的m大于或者等于n，比如从最初有6个数字的圆圈删除每次第6、7个数字）
• 特殊输入测试（圆圈中有0个数字）
• 性能测试（从最初有4000个数字的圆圈中每次删除第997个数字）

这篇关于圆圈中最后剩下的数字（不太理解方法2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---