约瑟夫环问题

一、问题描述

n个人从1开始编号，1，2，3，一直到n，数到第m个人出列，问剩下的最后的人的编号是多少？

二、解决思路

（1）双向链表循环链表模拟
（2）单向链表+双指针
（3）数组模拟单向链表
题目要求数m个人出列，我们数到m-1个人就好了。因为是单向的，可以获取下一个人的序号。

public class Main {
    public static void main(String[] args) {
        int n = 100;
        int m = 3;
        int[] list = new int[n+1];
        // 1、初始化队伍，数组代替链表，list[i]表示i的next
        for(int i=1; i<n;++i){
           list[i] = i+1;
        }
        list[n] = 1;
        // 2、准备开始数数
        int count = 0;
        int left_num = n;
        int cur = n;
        while(left_num != 1){
            while (count!=m-1){
               // 点下一个人,cur = cur.next
               cur = list[cur];
               count++;
            }
            // 此时数了m-1个人,接下来的第m个人需要出列
            // 此人需要出列
            int out_people = list[cur];
            System.out.print(out_people + " ");
            // 修改队伍  cur.next = cur.next.next
            list[cur] = list[out_people];
            left_num--;
            count = 0;
        }
        System.out.println(cur);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

代码比较简单，直接看就能看懂。属于简单模拟。