题目描述
约瑟夫问题,是经典的问题,假设有n个士兵围着成为一圈,他们的号码是从0到n-1,那么从第一个开始报数,第一个报数0,每次加1,报到n-1的时候,报n-1的士兵出圈,下一个士兵接着从0开始报数,这样循环,值得最后,剩下一个士兵,那这个士兵就是胜利者。
现在给出士兵数量m,和报数n,求解最后胜利的是几号士兵?
示例
输入
5,3
输出
2
思路以及解答
这道题,由于是围成一个圆圈,涉及到不断删除士兵(出圈)的问题,所以用链表比较适合。判断如果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; }}
【刷题笔记】
Github仓库地址:https://github.com/Damaer/codeSolution
笔记地址:https://damaer.github.io/codeSolution/
【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。
平日时间宝贵,只能使用晚上以及周末时间学习写作,关注我,我们一起成长吧~