太透徹了：約瑟夫環的三種解法

前言

約瑟夫環問題是算法中相當經典的一個問題，其問題理解是相當容易的，並且問題描述有非常多的版本，並且約瑟夫環問題還有很多變形，這篇約瑟夫問題的講解，一定可以帶你理解通通！

什麼是約瑟夫環問題？

約瑟夫環問題在不同平臺被 "優化" 描述的不一樣，例如在牛客劍指 offer 叫孩子們的遊戲，還有叫殺人遊戲，點名…… 最直接的感覺還是力扣上劍指 offer62 的描述：圓圈中最後剩下的數字。

問題描述：

0,1,···,n-1 這 n 個數字排成一個圓圈，從數字 0 開始，每次從這個圓圈裏刪除第 m 個數字（刪除後從下一個數字開始計數）。求出這個圓圈裏剩下的最後一個數字。

例如，0、1、2、3、4 這 5 個數字組成一個圓圈，從數字 0 開始每次刪除第 3 個數字，則刪除的前 4 個數字依次是 2、0、4、1，因此最後剩下的數字是 3。

當然，這裏考慮 m，n 都是正常的數據範圍，其中

對於這個問題，你可能腦海中有了印象，想着小時候村裏一羣孩子坐在一起，從某個開始報數然後數到幾齣列，下一個重新開始一直到最後一個。不同人用不同方法解決，青銅直接模擬，鑽石會優化一下，王者用公式，下面詳細給大家講解思路。

循環鏈表模擬

這個問題最本質其實就是循環鏈表的問題，圍成一個圈之後，就沒有結尾這就是一個典型的循環鏈表嘛！一個一個順序報數，那不就是鏈表的遍歷枚舉嘛！數到對應數字的出列，這不就是循環鏈表的刪除嘛！

鏈表模擬

並且這裏還有非常方便的地方：

當然也有一些需要注意的地方

這樣，思路明確，直接開擼代碼：

class Solution {
    class node//鏈表節點
    {
        int val;
        public node(int value) {
            this.val=value;
        }
        node next;
    }
    public int lastRemaining(int n, int m) {
        if(m==1)return n-1;//一次一個直接返回最後一個即可
        node head=new node(0);
        node team=head;//創建一個鏈表
        for(int i=1;i<n;i++)
        {
            team.next=new node(i);
            team=team.next;
        }
        team.next=head;//使形成環
        int index=0;//從0開始計數
        while (head.next!=head) {//當剩餘節點不止一個的時候
            //如果index=m-2 那就說明下個節點(m-1)該刪除了
            if(index==m-2)
            {
                head.next=head.next.next;
                index=0;
            }
            else {
                index++;
            }
            head=head.next;
        }
        return head.val;
    }
}

當然，這種算法太複雜了，大部分的 OJ 你提交上去是無法 AC 的，因爲超時太嚴重了，具體的我們可以下面分析。

有序集合模擬

上面使用鏈表直接模擬遊戲過程會造成非常嚴重非常嚴重的超時，n 個數字，數到第 m 個出列。因爲 m 如果非常大遠遠大於 n，那麼將進行很多次轉圈圈。

所以我們可以利用求餘的方法判斷等價最低的枚舉次數，然後將其刪除即可，在這裏你可以繼續使用自建鏈表去模擬，上面的 while 循環以及上面只需添加一個記錄長度的每次求餘算圈數即可：

int len=n;
while (head.next!=head) {
  if(index==(m-2)%len)
  {
    head.next=head.next.next;
    index=0;
    len--;
  }
  else {
    index++;
  }
  head=head.next;
}

但我們很多時候不會手動去寫一個鏈表模擬，我們會藉助 ArrayList 和 LinkedList 去模擬，如果使用 LinkedList 其底層也是鏈表，使用 ArrayList 的話其底層數據結構是數組。不過在使用 List 其代碼方法一致。

List 可以直接知道長度，也可刪除元素，使用 List 的難點是一個順序表怎麼模擬成循環鏈表？

刪除 3 號下標

index=(index+m-1)%(list.size());

真實位置計算

class Solution {
    public int lastRemaining(int n, int m) {
        if(m==1)
            return n-1;
        List<Integer>list=new ArrayList<>();
        for(int i=0;i<n;i++)
        {
            list.add(i);
        }
        int index=0;
        while (list.size()>1)
        {
            index=(index+m-1)%(list.size());
            list.remove(index);
        }
        return list.get(0);
    }
}

遞歸公式解決

f(n,m)=(f(n-1,m)+m)%n
f(n,m)指n個人，報第m個編號出列最終編號

下面要認真看一下我的分析過程：

我們舉個例子，有0 1 2 3 4 5 6 7 8 9十個數字，假設 m 爲 3, 最後結果可以先記成 f(10,3)，即使我們不知道它是多少。

當進行第一次時候，找到元素2 刪除，此時還剩 9 個元素，但起始位置已經變成元素 3。等價成3 4 5 6 7 8 9 0 1這 9 個數字重寫開始找。

f(10,3) 刪除第一個數

此時這個序列最終剩下的一個值即爲 f(10,3)，這個序列的值和 f(9,3) 不同，但是都是 9 個數且 m 等於 3，所以其刪除位置是相同的，即算法大體流程是一致的，只是各位置上的數字不一樣。所以我們需要做的事情是找找這個序列上和 f(9,3) 值上有沒有什麼聯繫。

尋找過程中別忘記兩點，首先可通過 % 符號對數字有效擴充，即我們可以將3 4 5 6 7 8 9 0 1這個序列看成 (3,4,5,6,7,8,9,10,11)%10. 這裏的 10 即爲此時的 n 數值。

另外數值如果是連續的，那麼最終一個結果的話是可以找到聯繫的 (差值爲一個定製)。所以我們可以就找到 f(10,3) 和 f(9,3)值之間結果的關係，可以看下圖：

f(10,3) 刪除一次和 f(9,3)

所以 f(10,3) 的結果就可以轉化爲 f(9,3) 的表達, 後面也是同理：

f(10,3)=(f(9,3)+3)%10
f(9,3)=(f(8,3)+3)%9
……
f(2,3)=(f(1,3)+3)%2
f(1,3)=0

這樣，我們就不用模擬操作，可以直接從數值的關係找到遞推的關係，可以輕輕鬆鬆的寫下代碼：

class Solution {
    int index=0;
    public int lastRemaining(int n, int m) {
         if(n==1)
            return 0;      
        return (lastRemaining(n-1,m)+m)%n;
    }
}

但是遞歸效率因爲有個來回的規程，效率相比直接迭代差一些，也可從前往後迭代：

class Solution {
    public int lastRemaining(int n, int m) {
        int value=0;
            for(int i=1;i<=n;i++)
            {
                value=(value+m)%i;
            }
            return  value;
    }
}

結語

我想，通過本篇文章你應該掌握和理解了約瑟夫環問題，這種裸的約瑟夫環問題出現的概率很大，考察很頻繁，鏈表模擬是根本思想，有序集合模擬鏈表是提升，而公式遞推纔是最有學習價值的地方，如果你剛開始接觸不理解可以多看幾遍。如果能用公式遞推給面試官說兩句，講講原理，那一定會讓面試官眼前一亮的！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lK1GahUdsNPlBbluATVTeA

猜你喜歡