一、问题描述
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的nextfor(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.nextcur = list[cur];count++;}// 此时数了m-1个人,接下来的第m个人需要出列// 此人需要出列int out_people = list[cur];System.out.print(out_people + " ");// 修改队伍 cur.next = cur.next.nextlist[cur] = list[out_people];left_num--;count = 0;}System.out.println(cur);}
}
代码比较简单,直接看就能看懂。属于简单模拟。