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

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

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

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

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

当前位置： 算法 > 剑指offer > 剑指offer 62. 圆圈中最后剩下的数字

剑指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
输出: 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完整版

剑指offer