圆圈中最后剩下的数字

1、题目描述

0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求出这个圆圈里剩下的最后一个数字。

2、解题代码

(1)方法一

利用循环链表模拟这个过程,每找到一个要删除的数字就将其从循环链表里移除,直到找到最后的一个数字

public class LastNumberInCircle_45
{
    /************************************************************************
     * 解法1:利用循环链表。
     * @param n n个数字
     * @param m 每次删除第m个数字
     * @return 最后剩下的数字
     ************************************************************************/
    public int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m <1)
            return -1;

       CircleNode head = new CircleNode(0);
       CircleNode tail = head;
       for (int i = 1; i < n; ++i)
           tail = (tail.next = new CircleNode(i));

       //形成循环链表
       tail.next = head;
       while (tail != tail.next)
       {
           for (int i = 1; i < m; ++i)
               tail = tail.next;
           //此时tail 是要出列节点的前一个节点
           tail.next = tail.next.next;
       }

        return tail.value;
    }
}

class CircleNode
{
    int value;
    CircleNode next;

    public CircleNode(int value)
    {
        this.value = value;
    }
}

(2)方法二

试着找到每次被删除数字有哪些规律。首先定义一个关于n和m的方程f(n,m),表示在n个数字0,1,...,n-1中每次删除第m个数字最后剩下的数字。

  • 在这n个数字中,第一个被删除的数字是(m-1)%n记为k

k = (m-1)%n .......................................A

那么删除k之后剩下的n-1个数字0,1,...k-1,k+1,...,n-1,并且下一次删。除数字从k+1开始计数。相当于在剩下的序列中,k+1排在最前面,从而形成k+1,...,n-1,0,1,...k-1。该序列最后剩下的数字也是关于n和m的函数。由于这个序列的规律和前最初序列不一样,因此函数不同于最初序列,即为f'(n-1, m)。最初序列最后剩下的数字f(n,m)一定是删除一个数字之后的序列最后剩下的数字,即

f(n,m)=f'(n-1, m) .................................B

接下来,定义一个映射p,p(x) = (x-k-1)%n,它表示如果当前的数字是x,那么映射后的数字是(x-k-1)%n。该映射的你映射为p-1(x) = (x+k+1)%n。把剩下的这n-1个数字的序列k+1,...,n-1,0,1,...k-1做一个映射p,得到

k+1 --------------->0
k+2 --------------->1
...
n-1 ---------------->n-k-2
0 ------------------->n-k-1
1 ------------------->n-k
...
k-1 ----------------->n-2

由于映射之后的序列和最初的序列具有相同的形式,即都是从0开始的连续序列,因此仍然可以用函数f表示,记为f(n-1,m),映射之前的序列中最后剩下的数字

f'(n-1, m)=p-1[f(n-1, m)]=[f(n-1, m)+k+1]%n ..................................C

把A、B带入C得

f(n,m)=f'(n-1, m)=[f(n-1, m)+m]%n .................................................D

经过上面分析,得到一个递推公式。要得到n个数字的序列中最后剩下的数字,只需要得到n-1个数字的序列中最后剩下的数字,并以此类推。当n=1时,也就是序列中开始只有一个数字0,那么最后剩下数字也是0。把这种关系表示为

f(n,m) = 0...............................n=1
f(n,m)=[f(n-1, m)+m]%n.........n>1

编码如下

/********************************************************************************
     * 解法2:试着找到每次被删除的数字有哪些规律
     ****************************************************************************/
    public int LastRemaining_Solution2(int n, int m)
    {
        if(n < 1 || m < 1)
            return -1;

        int last = 0;
        for (int i = 2; i <= n; ++i)
            last = (last + m) % i;

        return last;
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本系列导航:剑指offer(第二版)java实现导航帖 面试题62:圆圈中最后剩下的数字 题目要求:0,1,2.....
    ryderchan阅读 944评论 0 0
  • 题目:0, 1, … , n-1 这 n 个数字排成一个圈圈,从数字 0 开始每次从圆圏里删除第 m 个数字。求出...
    jacky123阅读 1,227评论 0 1
  • 我,正在迷茫的路口;我,在做选择 从前,看到那些考研的学长学姐们从清晨到日暮的备考,我心里只有...
    我只能往前走阅读 138评论 0 0
  • 咳咳,最近两天都在适配iOS11和iPhone X,在项目中遇到比较麻烦的一个适配是:在导航栏上添加的UISear...
    Jvaeyhcd阅读 6,184评论 3 3
  • 一 黑暗。 无边的黑暗。她心口一紧,滞住呼吸,脚踝被人抓住了。 挣扎着大口大口地呼吸。她被人扯下湖水。越沉越深,无...
    浅浅浅白阅读 615评论 3 4