装逼！如何用一行代码解决约瑟夫环问题

分手后的思念是犯贱 2024-04-17 05:41 49阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 帅地

来源 | 苦逼的码农

约瑟夫环问题算是很经典的题了，估计大家都听说过，然后我就在一次笔试中遇到了，下面我就用 3 种方法来详细讲解一下这道题，最后一种方法学了之后保证让你可以让你装逼。

> 问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。

### 1、方法一：数组 ###

在大一第一次遇到这个题的时候，我是用数组做的，我猜绝大多数人也都知道怎么做。方法是这样的：

用一个数组来存放 1，2，3 … n 这 n 个编号，如图（这里我们假设n = 6, m = 3）

![640?wx\_fmt=png][640_wx_fmt_png]  
然后不停着遍历数组，对于被选中的编号，我们就做一个标记，例如编号 arr\[2\] = 3 被选中了，那么我们可以做一个标记，例如让 arr\[2\] = -1，来表示 arr\[2\] 存放的编号已经出局的了。 ![640?wx\_fmt=png][640_wx_fmt_png 1]

然后就按照这种方法，不停着遍历数组，不停着做标记，直到数组中只有一个元素是非 -1 的，这样，剩下的那个元素就是我们要找的元素了。我演示一下吧：

![640?wx\_fmt=png][640_wx_fmt_png 2]

这种方法简单吗？思路简单，但是编码却没那么简单，临界条件特别多，每次遍历到数组最后一个元素的时候，还得重新设置下标为 0，并且遍历的时候还得判断该元素时候是否是 -1。感兴趣的可以动手写一下代码，用这种数组的方式做，千万不要觉得很简单，编码这个过程还是挺考验人的。

这种做法的时间复杂度是 O(n \* m), 空间复杂度是 O(n);

### 2、方法二：环形链表 ###

学过链表的人，估计都会用链表来处理约瑟夫环问题，用链表来处理其实和上面处理的思路差不多，只是用链表来处理的时候，对于被选中的编号，不再是**做标记**，而是**直接移除**，因为从链表移除一个元素的时间复杂度很低，为 O(1)。当然，上面数组的方法你也可以采用移除的方式，不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下：

1、先创建一个环形链表来存放元素：

![640?wx\_fmt=png][640_wx_fmt_png 3]

2、然后一边遍历链表一遍删除，直到链表只剩下一个节点，我这里就不全部演示了

![640?wx\_fmt=png][640_wx_fmt_png 4]

代码如下：

// 定义链表节点
    class Node{
        int date;
        Node next;
    
        public Node(int date) {
            this.date = date;
        }
    }

核心代码

public static int solve(int n, int m) {
            if(m == 1 || n < 2)
                return n;
            // 创建环形链表
            Node head = createLinkedList(n);
            // 遍历删除
            int count = 1;
            Node cur = head;
            Node pre = null;//前驱节点
            while (head.next != head) {
                // 删除节点
                if (count == m) {
                    count = 1;
                    pre.next = cur.next;
                    cur = pre.next;
                } else {
                    count++;
                    pre = cur;
                    cur = cur.next;
                }
            }
            return head.date;
        }
    
        static Node createLinkedList(int n) {
            Node head = new Node(1);
            Node next = head;
            for (int i = 2; i <= n; i++) {
                Node tmp = new Node(i);
                next.next = tmp;
                next = next.next;
            }
            // 头尾串联
            next.next = head;
            return head;
        }

这种方法估计是最多人用的，时间复杂度为 O(n \* m),空间复杂度是 O(n)。

还有更好的方法吗？答有，请往下看

### 方法三：递归 ###

其实这道题还可以用递归来解决，递归是思路是**每次我们删除了某一个士兵之后，我们就对这些士兵重新编号，然后我们的难点就是找出删除前和删除后士兵编号的映射关系**。

我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

…

m - 1

m + 1

m + 2

进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：

删除前 --- 删除后

… --- …

m - 2 --- n - 2

m - 1 --- n - 1

m ---- 无(因为编号被删除了)

m + 1 --- 1(因为下次就从这里报数了)

m + 2 ---- 2

… ---- …

新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。

假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

这样，我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下：

> 注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

int f(int n, int m){
        if(n == 1)   return n;
        return (f(n - 1, m) + m - 1) % n + 1;
    }

我去，两行代码搞定，而且时间复杂度是 O(n)，空间复杂度是O(1)，牛逼！那如果你想跟别人说，我想一行代码解决约瑟夫问题呢？答是没问题的，如下：

int f(int n, int m){
        return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
    }

卧槽，以后面试官让你手写约瑟夫问题，你就扔这一行代码给它。

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png 5]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b66071555e324f2f8bb269627dd43a5d.png
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/79afe2a154134b3a9fb6bf7d59702e1d.png
[640_wx_fmt_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/da74c4e9577e4afdb12f54ae0e67f388.png
[640_wx_fmt_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/738703dc164b4580893773b064672cbc.png
[640_wx_fmt_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/be78425bbba04efb8234fdd2a61322bc.png
[640_wx_fmt_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/d3d1e311d00e475abbc0e2dd51d4b25a.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485538&idx=1&sn=03adf88e7fe8bb7a6df9c1f77b2651b4&chksm=fa0e67e3cd79eef576563214c99121e5dbfc6332a95e45eade3735efc1472ba4c27be086b9bd&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/452f6a12797c4e6cab3af425539bedae.png