本文鏈接：https://blog.csdn.net/m0_37907797/article/details/102990940
1马靠、方法一：數(shù)組
在大一第一次遇到這個(gè)題的時(shí)候，我是用數(shù)組做的蔼两，我猜絕大多數(shù)人也都知道怎么做甩鳄。方法是這樣的：
用一個(gè)數(shù)組來(lái)存放 1，2额划，3 … n 這 n 個(gè)編號(hào)妙啃，如圖（這里我們假設(shè)n = 6, m = 3）
然后不停著遍歷數(shù)組，對(duì)于被選中的編號(hào)俊戳，我們就做一個(gè)標(biāo)記揖赴，例如編號(hào) arr[2] = 3 被選中了，那么我們可以做一個(gè)標(biāo)記抑胎，例如讓 arr[2] = -1燥滑，來(lái)表示 arr[2] 存放的編號(hào)已經(jīng)出局的了。
然后就按照這種方法圆恤，不停著遍歷數(shù)組突倍，不停著做標(biāo)記，直到數(shù)組中只有一個(gè)元素是非 -1 的盆昙，這樣羽历，剩下的那個(gè)元素就是我們要找的元素了。我演示一下吧：
這種方法簡(jiǎn)單嗎淡喜？思路簡(jiǎn)單秕磷，但是編碼卻沒(méi)那么簡(jiǎn)單，臨界條件特別多炼团，每次遍歷到數(shù)組最后一個(gè)元素的時(shí)候澎嚣，還得重新設(shè)置下標(biāo)為 0疏尿，并且遍歷的時(shí)候還得判斷該元素時(shí)候是否是 -1。感興趣的可以動(dòng)手寫(xiě)一下代碼易桃，用這種數(shù)組的方式做褥琐，千萬(wàn)不要覺(jué)得很簡(jiǎn)單，編碼這個(gè)過(guò)程還是挺考驗(yàn)人的晤郑。
這種做法的時(shí)間復(fù)雜度是 O(n * m), 空間復(fù)雜度是 O(n);
2敌呈、方法二：環(huán)形鏈表
學(xué)過(guò)鏈表的人，估計(jì)都會(huì)用鏈表來(lái)處理約瑟夫環(huán)問(wèn)題造寝，用鏈表來(lái)處理其實(shí)和上面處理的思路差不多磕洪，只是用鏈表來(lái)處理的時(shí)候，對(duì)于被選中的編號(hào)诫龙，不再是做標(biāo)記析显，而是直接移除，因?yàn)閺逆湵硪瞥粋€(gè)元素的時(shí)間復(fù)雜度很低签赃，為 O(1)谷异。當(dāng)然，上面數(shù)組的方法你也可以采用移除的方式姊舵，不過(guò)數(shù)組移除的時(shí)間復(fù)雜度為 O(n)晰绎。所以采用鏈表的解決方法如下：
1、先創(chuàng)建一個(gè)環(huán)形鏈表來(lái)存放元素：
2括丁、然后一邊遍歷鏈表一遍刪除荞下，直到鏈表只剩下一個(gè)節(jié)點(diǎn)，我這里就不全部演示了
代碼如下：
// 定義鏈表節(jié)點(diǎn)
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;
// 創(chuàng)建環(huán)形鏈表
Node head = createLinkedList(n);
// 遍歷刪除
int count = 1;
Node cur = head;
Node pre = null;//前驅(qū)節(jié)點(diǎn)
while (head.next != head) {
// 刪除節(jié)點(diǎn)
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;
}
// 頭尾串聯(lián)
next.next = head;
return head;
}
這種方法估計(jì)是最多人用的史飞，時(shí)間復(fù)雜度為 O(n * m),空間復(fù)雜度是 O(n)尖昏。
方法三：遞歸
其實(shí)這道題還可以用遞歸來(lái)解決，遞歸是思路是每次我們刪除了某一個(gè)士兵之后构资，我們就對(duì)這些士兵重新編號(hào)抽诉，然后我們的難點(diǎn)就是找出刪除前和刪除后士兵編號(hào)的映射關(guān)系。
我們定義遞歸函數(shù) f(n吐绵，m) 的返回結(jié)果是存活士兵的編號(hào)迹淌，顯然當(dāng) n = 1 時(shí)，f(n, m) = 1己单。假如我們能夠找出 f(n唉窃，m) 和 f(n-1，m) 之間的關(guān)系的話纹笼，我們就可以用遞歸的方式來(lái)解決了纹份。我們假設(shè)人員數(shù)為 n, 報(bào)數(shù)到 m 的人就自殺。則剛開(kāi)始的編號(hào)為
…
1
…
m - 2
m - 1
m
m + 1
m + 2
…
n
…
進(jìn)行了一次刪除之后，刪除了編號(hào)為 m 的節(jié)點(diǎn)蔓涧。刪除之后件已，就只剩下 n - 1 個(gè)節(jié)點(diǎn)了，刪除前和刪除之后的編號(hào)轉(zhuǎn)換關(guān)系為：
刪除前 — 刪除后
… — …
m - 2 — n - 2
m - 1 — n - 1
m ---- 無(wú)(因?yàn)榫幪?hào)被刪除了)
m + 1 — 1(因?yàn)橄麓尉蛷倪@里報(bào)數(shù)了)
m + 2 ---- 2
… ---- …
新的環(huán)中只有 n - 1 個(gè)節(jié)點(diǎn)元暴。且刪除前編號(hào)為 m + 1, m + 2, m + 3 的節(jié)點(diǎn)成了刪除后編號(hào)為 1篷扩， 2， 3 的節(jié)點(diǎn)昨寞。
假設(shè) old 為刪除之前的節(jié)點(diǎn)編號(hào)瞻惋， new 為刪除了一個(gè)節(jié)點(diǎn)之后的編號(hào)，則 old 與 new 之間的關(guān)系為 old = (new + m - 1) % n + 1援岩。
注：有些人可能會(huì)疑惑為什么不是 old = (new + m ) % n 呢？主要是因?yàn)榫幪?hào)是從 1 開(kāi)始的掏导，而不是從 0 開(kāi)始的享怀。如果 new + m == n的話，會(huì)導(dǎo)致最后的計(jì)算結(jié)果為 old = 0趟咆。所以 old = (new + m - 1) % n + 1.
這樣添瓷，我們就得出 f(n, m) 與 f(n - 1, m)之間的關(guān)系了，而 f(1, m) = 1.所以我們可以采用遞歸的方式來(lái)做值纱。代碼如下：
int f(int n, int m){
if(n == 1) return n;
return (f(n - 1, m) + m - 1) % n + 1;
}
或
int f(int n, int m){
return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
