剑指offer46 圆圈中最后剩下的数

剑指offer46

圆圈中最后剩下的数

题目描述

首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

输入

5,3

输出

3

思路

以题目输入 n=5, m=3 为例说明（m-1=2）：

初 始：0 1 2 3 4

第一次：0 1 3 4

第二次：1 3 4

第三次：1 3

第四次：3

每次只移除一个元素，最多移除4次（n-1），且数组长度动态变化，因此考虑使用链表。

这是个约瑟夫环问题，但是绝对没必要去死记硬背数学公式，直接用链表模拟游戏过程即可。

代码

import java.util.LinkedList;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {

        //1.数学归纳法
        /**
        if(n<1 || m<1)return -1;
        int last = 0;
        for(int i=2;i<=n;i++){
            last=(last+m)%i;
        }
        return last;
        */

        //2.LinkedList 模拟游戏过程
        //这是个约瑟夫环问题，但是绝对没必要去死记硬背数学公式，直接用链表模拟游戏过程即可。
        LinkedList<Integer> list = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            list.add(i);
        }

        int temp=0;
        while(list.size()>1){
            temp = (temp+m-1)%list.size();
            list.remove(temp);
        }
        return list.size()==1?list.get(0):-1;
    }
}