剑指offer-46、孩⼦们的游戏(圆圈中最后剩下的数)
<h2 id="题目描述">题目描述</h2><p>有个游戏是这样的：⾸先，让 n 个⼩朋友们围成⼀个⼤圈，⼩朋友们的编号是0~n-1。然后，随机指定⼀个数 m ，让编号为0的⼩朋友开始报数。每次喊到 m-1 的那个⼩朋友要出列唱⾸歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下⼀个⼩朋友开始，继续 0... m-1报数....这样下去....直到剩下最后⼀个⼩朋友，可以不⽤表演，并且拿到⽜客礼品，请你试着想下，哪个⼩朋友会得到这份礼品呢？</p>
<p>示例<br>
输⼊：5,3<br>
输出：2</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="数组模拟">数组模拟</h3>
<p>通过布尔数组标记小朋友的出局状态</p>
<pre><code class="language-java">public class Solution {
public int lastRemaining(int n, int m) {
if (n <= 0 || m <= 0) return -1;
boolean[] out = new boolean; // 标记是否出局
int count = n; // 剩余人数
int index = 0; // 当前报数位置
int step = 0; // 报数计数器
while (count > 1) {
// 如果当前小朋友未出局，参与报数
if (!out) {
step++;
// 报到m-1的小朋友出局
if (step == m) {
out = true;// 标记出局
count--; // 剩余人数减1
step = 0; // 重置计数器
}
}
// 移动到下一个位置（循环）
index = (index + 1) % n;
}
// 找到最后一个未出局的小朋友
for (int i = 0; i < n; i++) {
if (!out) {
return i;
}
}
return -1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n×m)，最坏情况下每个小朋友都需要报数m次</li>
<li><strong>空间复杂度</strong>：O(n)，需要长度为n的布尔数组</li>
</ul>
<h3 id="循环链表">循环链表</h3>
<p>使用循环链表模拟小朋友围成的圈，将小朋友存入链表，循环删除第m个元素</p>
<pre><code class="language-java">public class Solution {
public int lastRemaining(int n, int m) {
if (n <= 0 || m <= 0) return -1;
List<Integer> 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);
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n×m)，需要遍历链表进行删除操作</li>
<li><strong>空间复杂度</strong>：O(n)，需要存储n个节点</li>
</ul>
<h3 id="数学归纳法推荐">数学归纳法（推荐）</h3>
<p>分析每次被删除的数字规律，直接计算出最后的数字，不需要模拟</p>
<pre><code class="language-java">F(N,M) = ( F(N−1,M) + M ) % N
</code></pre>
<p><strong>递推公式的推导过程：</strong></p>
<ol>
<li><strong>第一次删除</strong>：从0开始报数，删除第(m-1)%n个小朋友</li>
<li><strong>重新编号</strong>：删除后，从第m%n个小朋友开始重新编号：
<ul>
<li>旧编号：m%n, m%n+1, ..., n-1, 0, 1, ..., m%n-1</li>
<li>新编号：0, 1, 2, ..., n-2</li>
</ul>
</li>
<li><strong>映射关系</strong>：新编号x对应的旧编号为(x + m) % n</li>
</ol>
<p><strong>示例验证（n=5, m=3）：</strong></p>
<pre><code class="language-text">原始编号: 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) % 5
</code></pre>
<pre><code class="language-java">public 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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要n次递归调用</li>
<li><strong>空间复杂度</strong>：O(n)，递归调用栈深度</li>
</ul>
<h3 id="迭代优化">迭代优化</h3>
<p>将递归转为迭代，避免栈溢出风险，是生产环境的最佳选择</p>
<pre><code class="language-java">public 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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需一次循环</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19285929
頁:
[1]