微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 62. 圆圈中最后剩下的数字
本文链接:https://www.mianshi.online/2808.html

题目描述

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
输出: 2

限制:

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

题解 1

(模拟环形链表) O(nm) 超时

用 list 模拟环形链表,由于 list 不是环形结构,所以当迭代器走到链表末尾时,需要让其转到链表头部形成环

每次从迭代器指向的数开始数,数 m 次找到第 m 个数,将其删除,接着再从下一个位置开始数,循环此过程,直到环中只剩下一个数,就是答案

时间复杂度

环中总共有 n 个数字,需要删掉 n – 1 个数才能得到答案,每删除一个数需要迭代器移动 m – 1 次,所以时间复杂度为 O(nm)

空间复杂度

O(n)

C++ 代码

#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        list<int> nums;
        for (int i = 0; i < n; i ++ ) nums.push_back(i);
        
        // 从头开始报数,除去当前数外,还需循环 m - 1 次找到第 m 个数
        auto it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1)
        {
            while (k -- )
            {
                it ++ ;
                // 如果迭代器走到末尾将其移到开头继续寻找,形成环形链表
                if (it == nums.end()) it = nums.begin();
            }
            // 删除当前迭代器指定位置上的元素,返回下一个位置的迭代器
            it = nums.erase(it);
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();        
    }
};

题解 2

(推导递推式) O(n^2)

首先我们应该知道 f[i, m] 的含义是 i 个数字中删除第 m 个数字

f(n, m) 表示 n 个数字删除第 m 个数字,删除 m – 1,此时圆中的数字为 (0, 1, 2, … m – 2, m, m + 1 .. n – 1) (m – 1 被删掉了) f(n – 1, m) 表示 n – 1 个数字中删除第 m 个数字,开始数数前此时圆中的数字为 (m, m + 1, m + 2 … n – 1, n[0], n + 1[1], n + 2[2]…) % n 观察两组数字,可得递推式:f(n, m) = (f(n - 1, m) + m) % n

边界:当 n = 1 时圆中只有一个数字 0,返回 0 即可

时间复杂度

由 f[1, m] = 0 递推 n – 1 次就可以得到 f[n, m],所以时间复杂度为 O(n)

C++ 代码

class Solution {
public:
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};

Java 代码

class Solution {
    public int lastRemaining(int n, int m) {
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
}

Python 代码

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n == 1:
            return 0
        return (self.lastRemaining(n - 1, m) + m) % n

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版