约瑟夫环的三种解法（循环链表、数组和用数组模拟链表）

目录

前言

题目描述：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围：​

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例 1：

输入：5,2    

返回值：3    

说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开

1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开

1，3，5，从5开始报数，5->1，1->2编号为1的人离开

3，5，从3开始报数，3->1，5->2编号为5的人离开

最后留下人的编号是3      

示例 2：

输入：1,1

返回值：1

一、用循环链表实现

typedef struct Node
{
    int id;  // 编号（从 1 开始）
    struct Node* next;
}Node;

int ysf(int n, int m) 
{
    // 采用尾插法构造编号为 1 ~ n 的循环链表
    Node* phead = (Node*)malloc(sizeof(Node));  // 头指针
    phead->id = 1;
    Node* tail = phead;  // 尾指针
    for (int i = 2; i <= n; ++i)
    {
        Node* newnode = (Node*)malloc(sizeof(Node));
        newnode->id = i;
        newnode->next = NULL;
        tail->next = newnode;
        tail = newnode;
    }
    tail->next = phead;  // 让最后一个节点的 next 域指向第一个节点
    // 开始
    Node* cur = phead;
    Node* prev = tail;
    int count = 1;  // 计数器
    while (cur != prev)
    {
        if (count == m)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
            count = 1;  // 重置为 1
        }
        else 
        {
            prev = cur;
            cur = cur->next;
            ++count;
        }
    }
    int ret = cur->id;
    free(cur);
    return ret;
}

二、用数组实现

int ysf(int n, int m)
{
    int* is_out = (int*)calloc(n, sizeof(int));  // 0 表示在圈内，1 则表示退出
    int number = n;
    int count = 1;  // 计数器
    int i = 0;
    while (number > 1)
    {
        if (is_out[i] == 0)  // 圈内的人报数
        {
            if (count == m)
            {
                is_out[i] = 1;  // 退出
                --number;
                count = 1;  // 重置为 1
            }
            else
            {
                ++count;
            }
        }
        // 法一：
        ++i;
        if (i >= n)
        {
            i = 0;
        }
        // 法二：
        // i = (i + 1) % n;
    }
    for (i = 0; i < n; ++i)
    {
        if (is_out[i] == 0)
        {
            break;
        }
    }
    free(is_out);  // 释放动态开辟的内存空间
    return i + 1;  // 返回编号
}

三、用数组模拟链表实现

int ysf(int n, int m)
{
    int* next = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n - 1; ++i)
    {
        next[i] = i + 1;
    }
    // next[n - 1] == 0
    int cur = 0;
    int prev = n - 1;
    int count = 1;  // 计数器
    while (cur != prev)
    {
        if (count == m)
        {
            next[prev] = next[cur];
            next[cur] = -1;  // 退出
            cur = next[prev];
            count = 1;  // 重置为 1
        }
        else
        {
            prev = cur;
            cur = next[cur];
            ++count;
        }
    }
    free(next);  // 释放动态开辟的内存空间
    return cur + 1;  // 返回编号
}

创作不易，可以点点赞，如果能关注一下博主就更好了~