劍指Offer——圓圈中最後剩下的數字（JS實作） ｜刷題打卡

前言

掘金團隊号上線，助你 Offer 臨門！ 點選

檢視詳情

題目描述

解題思路

• 本題屬于約瑟夫環問題，屬于經典的數學問題
• 解題的核心思路在于：定義一個下标指針，在于下面的這個式子：
• head = （head + m - 1）% arr.length;

解題代碼

var lastRemaining = function(n, m) {
    let arr = []
    for (let i = 0;i < n;i++) {
        arr.push(i);
    }
    let flag = 0;
    while (arr.length !== 1) {
        flag = (flag + m - 1) % arr.length;
        arr.splice(flag,1);
    }
    
    return arr[0];
};

作者：Always_positive
連結：https://juejin.cn/post/6948417083923234823
來源：稀土掘金
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。      

總結

• 本題屬于一種數學題。
• 關鍵點在于明确什麼是約瑟夫環，以及删除第m個元素的下标是多少。
• 核心公式：head = （head + m - 1）% arr.length