一氣之下，我一行代碼搞定了約瑟夫環問題，面試官懵了

大家好，我是帥地，

對于約瑟夫環問題估計大家都聽說過，除非你剛剛讀大一，因為在大一大部分學校的課本都會降到這個演算法題，為了以防萬一你沒聽過，我還是給下問題的描述

問題描述：編號為 1-N 的 N 個士兵圍坐在一起形成一個圓圈，從編號為 1 的士兵開始依次報數（1，2，3…這樣依次報），數到 m 的 士兵會被殺死出列，之后的士兵再從 1 開始報數，直到最后剩下一士兵，求這個士兵的編號，

記得有一次，貌似是阿里的面試，面試官給了我一到原汁原味的約瑟夫好，好家伙，看我不把你秀一把，

不過，作為一個有著幾十場面試經驗的 xxx，我決定假裝用最土的方法入手，等面試官問我還有沒有其他方法時，我在一步步用更加牛逼的方法，

所以，第一種方法就是陣列，

1、方法一：陣列

實不相瞞，在大一第一次遇到這個題的時候，我是用陣列做的，我猜絕大多數人也都知道怎么做，方法是這樣的：

用一個陣列來存放 1，2，3 … n 這 n 個編號，如圖（這里我們假設n = 6, m = 3）

然后不停著遍歷陣列，對于被選中的編號，我們就做一個標記，例如編號 arr[2] = 3 被選中了，那么我們可以做一個標記，例如讓 arr[2] = -1，來表示 arr[2] 存放的編號已經出局的了，

然后就按照這種方法，不停著遍歷陣列，不停著做標記，直到陣列中只有一個元素是非 -1 的，這樣，剩下的那個元素就是我們要找的元素了，我演示一下吧：

這種方法簡單嗎？思路簡單，但是編碼卻沒那么簡單，臨界條件特別多，每次遍歷到陣列最后一個元素的時候，還得重新設定下標為 0，并且遍歷的時候還得判斷該元素時候是否是 -1，

但是，這種方法也不是一無是處，怎么說也體現了咱們的思維嚴謹，畢竟臨界條件這么多，我都能做對，嘿嘿，

感興趣的可以動手寫一下代碼，用這種陣列的方式做，千萬不要覺得很簡單，編碼這個程序還是挺考驗人的，

這種做法的時間復雜度是 O(n * m), 空間復雜度是 O(n);

面試官：還有其他方法嗎？

當然，面試要是不問，咱們也要跟面試官說，我突然想到了更好的方法啊，，，，，

第二種方法，只能掏出我大一第二學期學到的鏈表了，下面用鏈表跟大家講一講，

2、方法二：環形鏈表

學過鏈表的人，估計都會用鏈表來處理約瑟夫環問題，用鏈表來處理其實和上面處理的思路差不多，只是用鏈表來處理的時候，對于被選中的編號，不再是做標記，而是直接移除，因為從鏈表移除一個元素的時間復雜度很低，為 O(1)，當然，上面陣列的方法你也可以采用移除的方式，不過陣列移除的時間復雜度為 O(n)，所以采用鏈表的解決方法如下：

1、先創建一個環形鏈表來存放元素（注意，是環形鏈表哦）：

2、然后一邊遍歷鏈表一遍洗掉，直到鏈表只剩下一個節點，我這里就不全部演示了

代碼我就用 Java 寫了哈，

代碼如下：

// 定義鏈表節點
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 的人就自殺，則剛開始的編號為

…
1
…
m - 2

m - 1

m

m + 1

m + 2
…
n
…

進行了一次洗掉之后，洗掉了編號為 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，

有人可能看了會一臉懵逼？如果是這樣，那么我建議你自己找幾個例子模仿推導一下，估計就知道了

注：有些人可能會疑惑為什么不是 old = (new + m ) % n 呢？主要是因為編號是從 1 開始的，而不是從 0 開始的，如果 new + m == n的話，會導致最后的計算結果為 old = 0，所以 old = (new + m - 1) % n + 1.
這樣，我們就得出 f(n, m) 與 f(n - 1, m)之間的關系了，而 f(1, m) = 1.所以我們可以采用遞回的方式來做，代碼如下：

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

我去，兩行代碼搞定，而且時間復雜度是 O(n)，當然，空間復雜度還是 O(n)，因為會遞回會呼叫 n 次，

為了裝逼，我必須用用一行代碼來搞定，如下：

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

臥槽，以后面試官讓你手寫約瑟夫問題，你就扔這一行代碼給它，這里需要注意的是，如果 n 的數值太大，那么就不適合用遞回了，注意怕遞回太深，爆堆疊了

無論是面試還是提升自己的內容，演算法學習基本少不了，這里給大家推薦一份某 BAT 大佬總結的 Leetcode 刷題筆記，匯聚了上千道 leetcode 題解，并且代碼都是 beat 100%：：BAT 大佬分類總結的 Leetcode 刷題模版，助你搞定 90% 的面試

就算你現在不學演算法，那么這份筆記也值得你收藏，萬一有人問你 Leetcode 某道題解，或者有大神在討論題解，咱打開這份筆記，不管三七二十一，直接把最優解扔給他，然后退出群聊

鏈接：BAT 大佬分類總結的 Leetcode 刷題模版，助你搞定 90% 的面試

總結

不過那次筆試時，并沒有用遞回的方法做，而是用鏈表的方式做，，，，，那時，不知道原來還能用一行代碼搞定的，，，，歡迎各位大佬提供半行代碼搞定的方法！