本文共 5043 字，大约阅读时间需要 16 分钟。
题目描述
0，1，…，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里面删除第m个数字。求出这个圆圈里剩下的最后一个数字。
分析
约瑟夫环问题：利用java类库中的LinkedList（双向循环链表）可以实现模拟圆圈。
牛客AC：
package com.problem;import java.util.Iterator;import java.util.LinkedList;import java.util.List;public class JosephusRing { public static void main(String[] args) { JosephusRing josephusRing = new JosephusRing(); int n = 6; // 0,1,2,3,4,5 int m = 7; System.out.println(josephusRing.lastNumber(n, m)); } public int lastNumber(int n, int m) { if(n <= 0 || m <=0) return -1; // 填充链表 List list = new LinkedList (); for(int i = 0; i < n; i++) list.add(i); // 循环删除第m个元素 Iterator iterator = list.iterator(); int count = 0; while(list.size() != 1) { // 循环终止的条件为链表只剩下一个元素 // 每次数m个数 while(count < m) { // iterator()没有next时，使用listIterator() // 此处？？ if(!iterator.hasNext()) iterator = list.listIterator(); // 移动一次 iterator.next(); count++; //System.out.println("count: " + count + ", num : " + num); } // 删除第m个元素 iterator.remove(); count = 0; // 重新开始计数 } return list.get(0); }} 题目扩展
如果不是从第1个元素，而是从第k个元素开始进行计数，则iterator()需要先移动k步。这样考虑的代码更具有可扩展性。
代码：
/** * * @param n 数字的个数 * @param m 每次删除第m个数 * @param start 从第start个数开始 * @return */ public int lastNumber(int n, int m, int start) { if (n <= 0 || m <= 0) return -1; // 填充链表 List list = new LinkedList (); for (int i = 0; i < n; i++) list.add(i); /*** 先移动到第k个元素 ***/ Iterator iterator = list.iterator(); for(int i = 0; i < start - 1; i++) iterator.next(); // 循环删除第m个元素 int count = 0; while (list.size() != 1) { // 循环终止的条件为链表只剩下一个元素 // 每次数m个数 while (count < m) { // iterator()没有next时，使用listIterator() // 此处？？ if (!iterator.hasNext()) iterator = list.listIterator(); // 移动一次 iterator.next(); count++; // System.out.println("count: " + count + ", num : " + num); } // 删除第m个元素 iterator.remove(); count = 0; // 重新开始计数 } return list.get(0); } 不使用类库，自己设计数据结构，实现循环链表
设计Node类，包含value和next，构造循环链表，实现约瑟夫环。
代码：
package com.problem;public class JosephusRing2 { private class Node { int val; Node next; Node(int val) { this.val = val; } } public static void main(String[] args) { JosephusRing2 josephusRing = new JosephusRing2(); int n = 5; // 0,1,2,3,4,5 int m = 3; int start = 1; int lastNum = josephusRing.lastNumber(n, m, start); System.out.println("lastNum : " + lastNum); } public int lastNumber(int n, int m, int start) { if (n <= 0 || m <= 0) return -1; // 构建循环链表 Node head = new Node(0); // 头结点事先保存，连接尾节点 Node pNode = head; for (int i = 1; i < n; i++) { pNode.next = new Node(i); pNode = pNode.next; } pNode.next = head; // 首尾相连 // pNode 先移动到第start个节点 pNode = head; for (int i = 0; i < start - 1; i++) pNode = pNode.next; // 循环删除第m个节点 while (pNode != pNode.next) { // 要想删除第m个节点，需要找到第m个节点的前一个节点 // 即第m-1个节点，需要移动m-2步 for(int i = 1; i < m - 1; i++) pNode = pNode.next; //System.out.println("remove : " + pNode.next.val); pNode.next = pNode.next.next; // 删除第m个节点 pNode = pNode.next; //更新pNode为第m+1个 } return pNode.val; }} 创新解法
下面是剑指offer上的创新解法：理解的还不太透彻，可以作为参考。（假设从第1个数字开始计数）
定义一个关于n和m的方程 f(n,m) ，表示每次在n个数字0，1，…，n-1中每次删除第m个数字最后剩下的数字。
在这n个数字中，第一个被删除的数字是 (m−1)%n ，将其记为k，那么删除k之后剩下的n-1个数字为0，1，…，k-1，k+1，…，n-1，并且下一次删除从数字k+1开始计数。相当于在剩下的序列中，k+1排在最前面，形成k+1，…，n-1，0，1，…，k-1。该序列最后剩下的数字也是关于n和m的函数。由于这个序列的而规律和前面最初的序列不一样，因此该函数不同于前面的函数，记为 f′(n−1,m) 。最初序列最后剩下的数字 f(n,m) 一定是删除一个数字之后的序列最后剩下的数字，即有 f(n,m)=f′(n−1,m) 。
将剩下的n-1个数字的序列k+1，…，n-1，0，1，…，k-1做一个映射，映射的结果是形成一个从0到n-2的序列：
k+1 -> 0
k+2 -> 1 … n-1 -> n-k-2 0 -> n-k-1 1 -> n-k … k-1 -> n-2将映射定义为p，则 p(x)=(x−k−1) 。它表示如果映射前的数字是x，那么映射后的数字为 (x−k−1)%n 。该映射的逆映射为 p−1(x)=(x+k+1)%n 。
由于映射之后的序列和最初的序列具有同样的而形式，都是从0开始的连续序列，因此仍然可以用函数f来表示，记为 f(n−1,m) 。根据映射规则，映射之前的序列中最后剩下的数字
f′(n−1,m)=p−1[f(n−1,m)]=[f(n−1,m)+k+1]%n
把 k=(m−1)%n 代入，得到
f(n,m)=f′(n−1,m)=[f(n−1,m)+m]%n 。
因此得到最后的递推公式为：
f(n,m)={ 0[f(n−1,m)+m]%nn=1n>1
最后可以使用递归或者循环实现这个递推公式：
public int lastNumber(int n, int m) { if(n < 1 || m < 1) return -1; int last = 0; for(int i = 2; i <= n; i++) { last = (last + m) % i; } return last;} 参考
1. 何海涛，剑指offer名企面试官精讲典型编程题（纪念版），电子工业出版社 2.转载地址：http://wkxgi.baihongyu.com/