剑指Offer（四十六）-- 最后出圈的士兵（约瑟夫）
Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution
题目描述
约瑟夫问题，是经典的问题，假设有n个士兵围着成为一圈，他们的号码是从0到n-1，那么从第一个开始报数，第一个报数0，每次加1，报到n-1的时候，报n-1的士兵出圈，下一个士兵接着从0开始报数，这样循环，值得最后，剩下一个士兵，那这个士兵就是胜利者。
现在给出士兵数量m，和报数n，求解最后胜利的是几号士兵？
示例
输入
5,3
输出
3
思路以及解答
这道题，由于是围成一个圆圈，涉及到不断删除士兵（出圈）的问题，所以用链表比较适合。判断如果n，或者m小于等于0，非法情况直接返回-1。
先把0到n-1添加到list中，初始化计数器count为-1，索引位置为-1，返回的元素值为0，循环下面的计数，直到元素全部被删除。
为什么全部删除？这样我们可以直接取最后一个出圈的，也是最后一个待在圈子里面的。
每次计数器和索引位置都加1，然后索引位置如果超过了当前剩下的人数，就需要将索引index设置到开头位置。如果计数刚好等于m-1，那么就移除该索引的元素，并且保存被移除的元素值。同时将计数器count设置为-1，将索引位置退一位，因为已经把当前位置删除了。
代码实现如下：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public static void main(String[] args) {
Solution46 solution46 = new Solution46();
System.out.println(solution46.LastRemaining_Solution(5,3));
}
public int LastRemaining_Solution(int n, int m) {
if(n<=0||m<=0){
return -1;
}
List<Integer> list = new ArrayList<>();
for(int i = 0;i<n;i++){
list.add(i);
}
int count = -1;
int index = -1;
int result = 0;
while(!list.isEmpty()){
count++;
index++;
if(index>=list.size()){
index=0;
}
if(count==m-1){
result = list.remove(index);
count=-1;
index--;
}
}
return result;
}
}
上面的做法，时间复杂度是O(n^2), 每次删除一个节点，需要先找到那个节点，然后再删除，查找的时间复杂度为O(n),空间上，借助了一个队列，空间复杂度是O(n)。
第二种方法，是根据数学归纳法，分析每次被删除的数字规律，直接计算出最后的数字，不需要模拟：
F(N,M) = ( F(N−1,M) + M ) % N
代码实现：
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;
}
}【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作
腾讯云开发者
