CodeWars 題目

Link

難度

5 kyu

題目

是上一題 Josephus Permutation 的延伸，只是本次的所求不同。
上一次是求陣列被重新序列後的結果，這次是求被一一排除後，僅剩的最後一位數。
要做的事都不變，因此直接實作。

實作

function josephusSurvivor(n,k){
  if(k === 1) return n;
  let arr = new Array(n).fill(1).map((t,i) => ++i);
  let start = 1;
  
   while (arr.length >= 2) {
     arr = arr.filter((item) => {
       if (start === k) {
         start = 1;
         return false;
       } else {
         start++;
         return true;
       }
     });
   }
   return arr[0];
}

比較不同的是，這次傳入的序列是由自己產生的。
因此利用 new 建構長度為 n 的空陣列後，用 map 去遞增元素。

最後判斷 while 在陣列長度在變成 1 時結束，返回剩下唯一的元素。

他人的解法

function josephusSurvivor(n, k){
  return n < 1 ? 1 : (josephusSurvivor(n - 1, k) + --k) % n + 1;
}

利用遞迴技巧，如果 n 小於 1，直接輸出 1（這裡題目預設 n 與 k 都 ≥ 1）；

否則就帶入遞迴。

n - 1 是模擬 Josephus 的序列，7 → 6 → … → 1，這邊要被代表的是被刪除的元素。
k 表示要被移除的第 k 個元素，--k 是模擬 Josephus 被相隔的序列。

% n 是模擬 n 的長度形成的陣列頭尾相接循環，以確保不會超出陣列；最後的 + 1 是因為 Josephus 從 1 開始計數的。

假設 n = 5, k = 2。

n=5, k=2
(5-1, 2) + 1 % 5 + 1
(4-1, 2) + 1 % 4 + 1
(3-1, 2) + 1 % 3 + 1
(2-1, 2) + 1 % 2 + 1
 
n 數到 1
(1-1, 2) n < 1，return 1

遞迴開始倒推
1 + 1 % 2 => 0 + 1 = 1
1 + 1 % 3 => 2 + 1 = 3
3 + 1 % 4 => 0 + 1 = 1
1 + 1 % 5 => 2 + 1 = 3 ==> 輸出結果

心得

本次的最佳解結合了遞迴以及 % 巧妙的取餘。
其實題目本身的邏輯不難懂，甚至可以說是簡單。

但最佳解的運作方式比較不好懂，最後感覺是把自己的理解強硬地與題目結合的。