【剑指offer:圆圈中最后剩下的数字】JavaScript实现

题目描述:0,1,,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。例如,0、1、2、3、4 这 5 个数字组成一个圆圈,从数字 0 开始每次删除第 3 个数字,则删除的前 4 个数字依次是 2、0、4、1,因此最后剩下的数字是 3。

示例

输入: n = 5, m = 3
输出: 3

解法 1: 数学规律

可以发现:

  • n=1,最后剩下的数字是 0
  • n=2,最后剩下的数字是 (0 + m)%2
  • n=3,最后剩下的数字是 ((0 + m)%2 + m)%3

可以将上面的规律写成循环,第 n 次的结果等于:(上次一次结果 + m)%n

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-04-19-last-remain-number/
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function(n, m) {
    let result = 0;
    for (let i = 2; i <= n; ++i) {
        result = (result + m) % i;
    }
    return result;
};

时间复杂度是$O(N)$,空间复杂度是$O(1)$。

解法 2:模拟循环链表

尝试了下这种做法,会 TLE。因为时间复杂度是 O(m*n)。

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

#
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×