题目解析
两种方法的详细过程可参考文章:面试题
方法一:循环数组
- 假设当前索引号为
cur
,则下一个挑礼物的小朋友索引号为new = cur + m - 1
- 该小朋友不再回到圈内,从他下一个小朋友开始报数,因此他下一个小朋友的索引号为
cur = new
,即cur = cur + m - 1
- 由于小朋友围成了圈,因此索引号还需对总人数取模,即
cur = (cur + m - 1) % n
- 每轮离开一个小朋友,直至只剩下一个小朋友。
- 索引号记为当前剩余小朋友中的位置,编号则是小朋友原始的编号。题目要求输出剩下小朋友的编号,而计算过程是对岁引号进行操作,因此需要先存储每个编号对应的索引号。
代码实现
public int LastRemaining_Solution(int n, int m) { if(n == 0){ return -1; } int cur = 0; ArrayList<Integer> list = new ArrayList<>(); for(int i = 0;i < n;i++){ list.add(i); } while(n > 1){ cur = (cur + m - 1) % n; list.remove(cur); n--; } return list.get(0); }
- 时间复杂度:O(n)
- 空间复杂度:O(n)
方法二:递推公式
反向递推。
定义F(n,m)
表示最后剩下的小朋友的索引号,题目最终输出索引号对应的编号。推导F(n - 1,m)
:
以[0,1,2,3,4,5,6,7]为例,n = 8,m = 3,通过计算可知
F(8,3) = 6
F(7,3) = 3
F(6,3) = 0
F(5,3) = 3
F(4,3) = 0
F(3,3) = 1
F(2,3) = 1
F(1,3) = 0
通过反推可得(反推过程参考文章:面试题 ):
public int LastRemaining_Solution(int n, int m) { if(n == 0){ return -1; } int f = 0; for(int i = 2;i <= n;i++){ f = (f + m) % i; } return f; }
- 时间复杂度:O(n)
- 空间复杂度:O(1)