【算法题】约瑟夫问题

古城微笑少年丶 2023-10-06 16:51 21阅读 0赞

#### 目录 ####

*  1.问题定义
 *  2.思路
 *  3.代码实现 (Java)

## 1.问题定义 ##

n 个人围成一圈，其编号依次为 1 ~ n，从编号为 1 的人从 1 开始报数，报到 m 的人退出圈，然后下一个人继续从 1 开始报数…，如果循环进行，当圈中剩下一个人时，其直接出圈。请依次输出退圈的人的编号。

**样例 1：**  
输入：n = 6，m = 5  
输出：\[5, 4, 6, 2, 3, 1\]

**样例 2：**  
输入：n = 8，m = 10  
输出：\[2, 5, 1, 8, 4, 6, 3, 7\]

**提示：**  
1 <= n, m <= 1000

## 2.思路 ##

采用一维数组 nums\[\] 存放人的编号，先将 n 个人的编号存入 nums\[0\] ~ nums\[n - 1\] 中。从编号为 1 的人（下标为 0）开始循环，数到 m 的人 nums\[index\] 输出并将其从数组中删除（即将后面的元素前移一个位置），因此每次删除的起始位置就是上次删除的出列位置。反复执行直到 n 个人全部出圈为止。

## 3.代码实现 (Java) ##

class Solution {
        
        public static int[] JosephusProblem(int n, int m) {
        
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
        
                nums[i] = i + 1;
            }
            int k = 0;
            int[] res = new int[n];
            int index = 0;
            //目前剩余人数为 i
            for (int i = n; i >= 1; i--) {
        
                index = (index + m - 1) % i;
                res[k++] = nums[index];
                for (int j = index + 1; j <= i - 1; j++) {
        
                    nums[j - 1] = nums[j];
                }
            }
            return res;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题】约瑟夫问题

目录 1.问题定义 2.思路 3.代码实现 (Java) 1.问题定义 n 个人围成一圈，其编号依次为 1 ~ n，从编号为 1 的人从 1 开

古城微笑少年丶/ 2023年10月06日 16:51/ 0 赞/ 22 阅读

相关约瑟夫问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？ ![Center][] 第一种方法：循环思想

待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 192 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被

￡神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 182 阅读

相关约瑟夫问题

约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis

分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 185 阅读

相关约瑟夫算法

声明：本文仅为个人查阅方便所转，版权为原文作者本算法仅适用于找出最后的胜利者，而不是得到出列序列。此方法从考虑n-1个人中最终胜利者（最后一个没有出列的人是谁），递推到

柔光的暖阳◎/ 2022年06月12日 06:13/ 0 赞/ 131 阅读

相关约瑟夫问题

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017

╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 285 阅读

相关约瑟夫问题

1.知识点：循环链表 2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号 3.注意事项：

心已赠人/ 2022年05月30日 04:46/ 0 赞/ 180 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人

我就是我/ 2022年05月16日 06:06/ 0 赞/ 193 阅读

相关约瑟夫问题

约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述：开始有5个人围成圆形，从0号开始，数2个人，谁被数到就

灰太狼/ 2022年04月16日 00:46/ 0 赞/ 206 阅读

相关算法：约瑟夫环问题

问题描述：n个人围成一圈，从编号为k的人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，求最后一个出圈的人 / arr a

梦里梦外;/ 2022年01月27日 13:51/ 0 赞/ 254 阅读