剑指offer---- 圆圈中剩下的数----java实现

亦凉 2022-09-23 12:50 107阅读 0赞

**经典解法：**

（1）模拟一个循环数组，一共n个人，从零开始编号，设置一个变量i记录已经走过的编号，当编号i==n时，就将其值置为1，从而模拟出一个首位相连的环形数组。

（2）从0开始报号，报到第m-1的时候出列该位置的人，设置变量step，当step==m-1时，就数组对应值设为true，下次跳过此位置的人。

（3）因为要找到数组最后剩下的那个人，也就是要让n-1个人出列，那么设置一个变量并赋予初始值n-1，当其值变0的时候，循环队列就剩下一个人未出列。

public int LastRemaining_Solution(int n, int m) 
        {
            if(n <= 0 || m <= 0)
            {
            	return -1;
            }
            boolean [] array = new boolean[n];
            int count = n -1;//存放圈中还未出列过的人
            int step = -1; //存放已经本次报号中已经报的的号
            int i = -1;//计算一圈从0到n-1走到哪个编号了，走到n-1编号，置零；
            while(count > 0)
            {
            	//统计这一圈已经走到哪个编号，走到n-1编号置零
            	i++;
            	if(i == n )
            		i = 0;
            	//如果这个编号已经出列过。经过时就跳过，否则就报号
            	if(array[i] == true)
            	{
            	  continue;
            	}
                step++;
            	if(step == m-1)//当报到m-1号时，讲这个编号的小朋友出列也就是数组对应值置为true，下次再从0开始报号，为出列人数减一。
            	{
            		array[i] = true;
            		step = -1;
            		count--;
            	}
            }
            for(int j=0;j<array.length;j++)
            {
                if(!array[j])
                {
                    return j;
                }
            }
            return -1;
        }

**新方法**

当只有一个人的时候，编号为0将其返回

当有n个人的时候，走到第m-1个编号时，将m-1对应的人出列，剩下的n-1个人，将从m开始，可以采递归的方式；

public int LastRemaining_Solution(int n, int m)
        {
            if(n<=0 || m<= 0)
                return -1;
            if(n == 1)
                return 0;
            else
            {
                return (LastRemaining_Solution(n-1,  m)+m)%n;
            }
             
        }

** **