题目:0,1,2,……,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
法一:用环形链表模拟圆圈的经典算法(时间复杂度O(nm),空间复杂度O(n))
法二:分析数学规律的高效算法。(时间复杂度O(n),空间复杂度O(1))
http://www.blogjava.net/rorely/archive/2010/01/15/309732.html
//约瑟夫环,通过测试 /* OFFER P288:0,1,2,……,n-1这n个数字组成圆圈,从0开始每次从这个圆圈里删除第m个数字。求最后一个剩下的数字 JAVA面宝P194:30个人围成一圈,数到9的人出列,求最后剩下的15个人 */ public class JosephuseRing{ public static void main(String[] args){ int data[]={0,1,2,3,4}; josephuseRing(data,3); } public static void josephuseRing(int data[], int n){ int len=data.length;//初始长度,以后出圈一个,长度就减一 int last=-1; //保存最后一个数 int i=0; //i为元素下表 int j=1; //j代表当前要报的数 while(len>0){ if(data[i%data.length] != -1){//非空位 if(j%n==0){//找到要出圈的人,并把圈中人数减一 //System.out.print(data[i%data.length]+" "); last=data[i%data.length]; data[i%data.length]=-1;//输出后将其值置为-1,即无效值 j=1; i++; len--; }else{ i++; j++; } }else{//遇到空位了,就跳到下一位,但j不加一,也就是这个位置没有报数 i++; } } System.out.println("the last number is "+last); } }