思路及解答数组模拟通过布尔数组标记小朋友的出局状态javapublic class Solution { public int lastRemaining(int n, int m) { if (n 0 || m 0) return -1; boolean[] out new boolean[n]; // 标记是否出局 int count n; // 剩余人数 int index 0; // 当前报数位置 int step 0; // 报数计数器 while (count 1) { // 如果当前小朋友未出局参与报数 if (!out[index]) { step; // 报到m-1的小朋友出局 if (step m) { out[index] true; // 标记出局 count--; // 剩余人数减1 step 0; // 重置计数器 } } // 移动到下一个位置循环 index (index 1) % n; } // 找到最后一个未出局的小朋友 for (int i 0; i n; i) { if (!out[i]) { return i; } } return -1; } }时间复杂度O(n×m)最坏情况下每个小朋友都需要报数m次空间复杂度O(n)需要长度为n的布尔数组循环链表使用循环链表模拟小朋友围成的圈将小朋友存入链表循环删除第m个元素javapublic class Solution { public int lastRemaining(int n, int m) { if (n 0 || m 0) return -1; ListInteger list new LinkedList(); // 初始化链表存入所有小朋友编号 for (int i 0; i n; i) { list.add(i); } int index 0; // 当前指针位置 while (list.size() 1) { // 计算要删除的位置(当前索引 m-1) % 当前大小 index (index m - 1) % list.size(); list.remove(index); // 删除后index自动指向下一个元素不需要移动 } return list.get(0); } }时间复杂度O(n×m)需要遍历链表进行删除操作空间复杂度O(n)需要存储n个节点数学归纳法推荐分析每次被删除的数字规律直接计算出最后的数字不需要模拟javaF(N,M) ( F(N−1,M) M ) % N递推公式的推导过程第一次删除从0开始报数删除第(m-1)%n个小朋友重新编号删除后从第m%n个小朋友开始重新编号旧编号m%n, m%n1, ..., n-1, 0, 1, ..., m%n-1新编号0, 1, 2, ..., n-2映射关系新编号x对应的旧编号为(x m) % n示例验证n5, m3text原始编号: 0, 1, 2, 3, 4 第一次删除编号2 → 剩余: 0, 1, 3, 4 重新编号: 3→0, 4→1, 0→2, 1→3 f(5,3) (f(4,3) 3) % 5javapublic class Solution { public int LastRemaining_Solution(int n, int m) { if (n 0 || m 0) { return -1; } int result 0; for (int i 2; i n; i) { result (result m) % n; } return result; } }时间复杂度O(n)需要n次递归调用空间复杂度O(n)递归调用栈深度迭代优化将递归转为迭代避免栈溢出风险是生产环境的最佳选择javapublic class Solution { public int lastRemaining(int n, int m) { if (n 0 || m 0) return -1; int result 0; // f(1, m) 0 // 从2个人情况开始逐步计算到n个人 for (int i 2; i n; i) { result (result m) % i; } return result; }
