剑指offer | 面试题49：圆圈中最后剩下的数字

千羽

发布于 2022-04-12 14:32:05

2390

发布于 2022-04-12 14:32:05

死磕算法系列文章

“Leetcode : https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_49_lastRemaining/Solution.java

剑指 Offer 62. 圆圈中最后剩下的数字

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

示例 1:

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

示例 2:

输入: n = 10, m = 17
输出:

利用公式法：f[n] = (f[n-1] + k) mod n，或使用循环链表实现

“来吧，一图胜千言。如下图所示，为 n = 5 , m = 3 时的状态转移和对应的模拟删除过程。

复杂度分析：

时间复杂度 O(n)： 状态转移循环 n - 1 次使用 O(n) 时间，状态转移方程计算使用 O(1) 时间；
空间复杂度 O(1) ： 使用常数大小的额外空间；

package com.nateshao.sword_offer.topic_49_lastRemaining;

/**
 * @date Created by 邵桐杰 on 2022/2/24 21:51
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int i = lastRemaining(5, 3);
        System.out.println("i = " + i);
    }
    public static int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            // i 个人时删除数的索引等于 i-1 个人时删除数的索引+k(再对i 取余)
            x = (x + m) % i;
        }
        return x;
    }
}

参考文章：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-02-27，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树