首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【剑指offer:圆圈中最后剩下的数字】JavaScript实现

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

作者头像
心谭博客
发布2020-04-21 11:56:53
7280
发布2020-04-21 11:56:53
举报
文章被收录于专栏:YuanXinYuanXin

题目描述: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)。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-04-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解法 1: 数学规律
  • 解法 2:模拟循环链表
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档