题目：0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。
练习地址
https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
经典的解法，用环形链表模拟圆圈
import java.util.LinkedList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 0; i < n; i++) {
numbers.add(i);
}
int current = 0;
while (numbers.size() > 1) {
current = (current + m - 1) % numbers.size();
numbers.remove(current);
}
return numbers.getFirst();
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
创新的解法，拿到 Offer 不在话下
public class Solution {
public int LastRemaining_Solution(int n, 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;
}
}
递推公式：f(n,m) = [f(n-1,m)+m]%n，n>1。
公式推理过程可以见书 P302。
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
