詳解基於C++實現約瑟夫環問題的三種解法

一、前言

什麼是約瑟夫環問題?

約瑟夫環問題在不同平臺被”優化”描述的不一樣,例如在牛客劍指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都是正常的數據范圍,其中

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

對於這個問題,你可能腦海中有瞭印象,想著小時候村裡一群孩子坐在一起,從某個開始報數然後數到幾出列,下一個重新開始一直到最後一個。

二、循環鏈表模擬

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

並且這裡還有非常方便的地方:

  • 循環鏈表的向下枚舉不需要考慮頭尾問題,直接node=node.next向下
  • 循環聊表的刪除也不需要考慮頭尾問題,直接node.next=node.next.next刪除

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

  • 形成環形鏈表很簡單,隻需要將普通鏈表的最後一個節點的next指向第一個節點即可
  • 循環鏈表中隻有一個節點的時候停止返回,即node.next=node的時候
  • 刪除,需要找到待刪除的前面節點,所以我們刪除計數的時候要少即一位,利用前面的那個節點直接刪除後面節點即可

這樣,思路明確,直接開擼代碼:

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如果非常大遠遠大於m,那麼將進行很多次轉圈圈。

所以我們可以利用求餘的方法判斷等價最低的枚舉次數,然後將其刪除即可,在這裡你可以繼續使用自建鏈表去模擬,上面的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的難點是一個順序表怎們模擬成循環鏈表?

咱們仔細思考:假設當前長度為n,數到第m個(通過上面分析可以求餘讓這個有效的m不大於n)刪除,在index位置刪除。那麼刪除後剩下的就是n-1長度,index位置就是表示第一個計數的位置,我們可以通過求餘得知走下一個刪除需要多少步,那麼下個位置怎麼確定呢?

你可以分類討論看看走的次數是否越界,但這裡有更巧妙的方法,可以直接求的下一次具體的位置,公式就是為:

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

因為index是從1計數,如果是循環的再往前m-1個就是真正的位置,但是這裡可以先假設先將這個有序集合的長度擴大若幹倍,然後從index計數開始找到假設不循環的位置index2,最後我們將這個位置index2%(集合長度)即為真正的長度。

使用這個公式一舉幾得,既能把上面m過大循環過多的情況解決,又能找到真實的位置,就是將這個環先假設成線性的然後再去找到真的位置,如果不理解的話可以再看看這個圖:

這種情況的話大部分的OJ是可以勉強過關的,面試官的層面也大概率差不多的,具體代碼為:

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);
    }
}

四、遞歸公式解決

我們回顧上面的優化過程,上面用求餘可以解決m比n大很多很多的情況(即理論上需要轉很多很多圈的情況)。但是還可能存在n本身就很大的情況,無論是順序表ArrayList還是鏈表LinkedList去頻繁查詢、刪除都是很低效的。

所以聰明的人就開始從數據找一些規律或者關系。

先拋出公式:

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(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)+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;
    }
}

五、結語

我想,通過本篇文章你應該掌握和理解瞭約瑟夫環問題,這種裸的約瑟夫環問題出現的概率很大,考察很頻繁,鏈表模擬是根本思想,有序集合模擬鏈表是提升,而公式遞推才是最有學習價值的地方,如果你剛開始接觸不理解可以多看幾遍。

以上就是詳解基於C++實現約瑟夫環問題的三種解法的詳細內容,更多關於C++ 約瑟夫環的資料請關註WalkonNet其它相關文章!

推薦閱讀: