题目描述
0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
解题思路
思路一,直接使用对列模拟
public int lastRemaining(int n, int m) {Queue<Integer> queue = new LinkedList<>(), tmpQ = new LinkedList<>();for (int i = 0; i < n; i++) {queue.add(i);}while (queue.size() > 1) { //循环1int len = queue.size();int k = 0;while (k < (m - 1) % len) { //循环2tmpQ.add(queue.poll());k++;}queue.remove();//移出第m个while (!tmpQ.isEmpty()) {queue.add(tmpQ.poll());}}return queue.peek();}
以lastRemaining(5,3)为例,初始化对列,queue =[0,1,2,3,4]。
第一次移出(数2个到tmpQ中):tmpQ:[0,1] 。移出第3个:queue.poll(),此时queue为:[3,4]
移除后产生的新数组,将tmpQ加入到queue尾部即可:[3,4,0,1]
同理可得,第二次移出数字0,移出后的queue:[1,3,4]
第三次移出数字4,移出后的queue:[1,3]
第4次移出数字1,移出后的queue:[3]
此时对列queue只剩数字3,返回即可
复杂度分析
外层while循环1需要遍历n-1次,内层while循环2需要遍历m次,总的时间复杂度为O(m*n),当m、n比较大时,程序执行会很慢。
思路二,动态规划
输入n=5,m=3,记该问题为【5,3】问题,设解(即最后留下的数字)为:F(5)
- 【5,3】问题:数字环为:0 1 2 3 4 ,解为F(5)
- 【4,3】问题:数字环为:0 1 2 3 , 解为F(4)
对于【5,3】问题,首轮删除环中第3个数字后,得到一个长度为4的环:3 4 0 1。可以看到也变成了一个【4,3】问题,只是环不再是0 1 2 3。将【4,3】问题和【5,3】删除一轮后的环对照来看,即:
环a. 3 4 0 1 ==>【5,3】删除首轮后的环
环b. 0 1 2 3 ==>【4,3】的环,即F(4)
假设 F(4)=1,那么【5,3】删除后的解一定等于4(即a,b两者都是从4个数字里面删除第3个数字,最后留下的数字的索引一定是相等的),所以只需找到a,b环中数字的对应关系即可有F(n-1)推出F(n)
观察可得到下列对应关系:
F ( n ) = ( F ( n − 1 ) + m ) % n F(n)=(F(n-1)+m)\%n F(n)=(F(n−1)+m)%n
而 F ( 1 ) = 0 F(1)=0 F(1)=0,所以可以直接用递归完成
public int lastRemaining2(int n, int m) {if (n == 1) return 0;return (lastRemaining2(n - 1, m) + m) % n;}
如果不用递归,通过动态规划也可,两者思路是一样的(已知F(1),通过递推关系得到F(n))
public int lastRemaining(int n, int m) {int a = 0;for (int i = 2; i <= n; i++) {a = (a + m) % i;}return a;}