⭐ 题目日期：

字节 - 2024/10/25

🌳 题目描述：

编号 1~100 号的小朋友围成一个圈，进行循环报数，报到 7 的小朋友出局，最后剩下来的人编号是多少？

🕵🏽 面试评估：

这道题是一个经典的数学与算法问题约瑟夫环问题，用于考察候选人的抽象建模能力、算法设计能力、代码实现能力以及优化思维。通过讨论数学法和模拟法的优缺点，还可以进一步考察候选人的深度思考能力和技术广度。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

方法一：模拟法

模拟整个报数过程，用循环链表模拟环，逐个移除出局的小朋友，直到只剩下一个人。

方法二：数学法

n 个人围成一个环，0， 1， 2， 3， 4， 5， 6， 7， 8，... n - 1，

k = 7, 则第一个出局的人 index = 6, 剩下的人为：

从接下来第一个报数开始排列：7, 8, ..., n -1, n, n + 1, n + 2, n + 3, n + 4, n + 5

将所有的编号减 k = 7, 得到：

0, 1, ..., n - 8, n - 7, n - 6, n - 5, n - 4, n - 3, n - 2

形成了一个由 n - 1 个人组成的新的约瑟夫环, 假设 f(n - 1) 是当前 n - 1 最后剩下来的那个人的编号，则有：

f(n) = (f(n - 1) + k) % n;

基准：f(1) = 0, 当只有一个人的时候，肯定会剩下来，索引为 0；

有了递归公式和基准，我们就能算出 f(n)

💻代码 (Java、Python)：

方法一：模拟法

Java

class Person {
    int id;
    Person next;
    Person(int id) {
        this.id = id;
    }
}

public int findLastPerson(int n, int k) {
    // 构建环形链表
    Person head = new Person(1);
    Person cur = head;
    for (int i = 2; i <= n; i++) {
        cur.next = new Person(i);
        cur = cur.next;
    }
    
    // 尾节点连接到头节点，形成环
    cur.next = head;

    cur = head;
    int count = n;
    while (count > 1) {
        // 找到要删除节点的前一个节点
        for (int i = 1; i < k - 1; i++) {
            cur = cur.next;
        }
        // 删除节点
        cur.next = cur.next.next;
        // 移动到下一个节点
        cur = cur.next;
        count--;
    }

    // 返回最后剩下的小朋友编号
    return cur.id;
}

Python

class Person:
    def __init__(self, id):
        self.id = id
        self.next = None

def find_last_person(n, k):
    # 构建环形链表
    head = Person(1)
    cur = head
    for i in range(2, n + 1):
        cur.next = Person(i)
        cur = cur.next
    cur.next = head  # 尾节点连接到头节点，形成环

    cur = head
    count = n
    while count > 1:
        # 找到要删除节点的前一个节点
        for _ in range(k - 2):
            cur = cur.next
        # 删除节点
        cur.next = cur.next.next
        # 移动到下一个节点
        cur = cur.next
        count -= 1

    return cur.id  # 返回最后剩下的小朋友编号

方法二：数学法

Java

public int findLastPerson(int n, int k) {
    int survivor = 0; // 初始时只有一人，索引为 0
    for (int i = 2; i <= n; i++) {
        survivor = (survivor + k) % i; 
    }
    
    return survivor + 1; // 转换为 1-based 编号
}

Python

def find_last_person(n, k):
    survivor = 0  # 初始时只有一人，索引为 0
    for i in range(2, n + 1):
        survivor = (survivor + k) % i

    return survivor + 1  # 转换为 1-based 编号

🚵🏻复杂度分析：

模拟法:

时间复杂度：O(kn), 每删除一个节点需要走 k 步，一共删除 n - 1 个节点，总的时间复杂度为 O(kn)

空间复杂度：O(n), 构建长度为 n 的循环链表

数学法：

时间复杂度：O(n), 递归公式 n 步

空间复杂度：O(1)