首页 > 试题广场 >

孩子们的游戏(圆圈中最后剩下的数)

[编程题]孩子们的游戏(圆圈中最后剩下的数)

热度指数：414497 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

数据范围： $1 \le n \le 5000$ ， $1 \le m \le 10000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

5,3

输出

示例2

输入

2,3

输出

说明

有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物

示例3

输入

10,17

输出

算法知识视频讲解

查看答案及解析

推荐

张佃鹏

如果只求最后一个报数胜利者的话，我们可以用数学归纳法解决该问题，为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。

现在我们把他们的编号做一下转换：

k --> 0

k+1 --> 1

k+2 --> 2

...

k-2 --> n-2

k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n。

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。

递推公式

f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1。

class Solution {
public:
    int LastRemaining_Solution(unsigned int n, unsigned int m)
    {
        if(n==0)
            return -1;
        if(n==1)
            return 0;
        else
            return (LastRemaining_Solution(n-1,m)+m)%n;
    }
};

编辑于 2015-08-18 23:33:31 回复(68)

Java

练习一坤年

dp 的思路 dp[i] 表示第i个数时胜利者的下标

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int LastRemaining_Solution (int n, int m) {
        // write code here
        int res=0;
        for(int i=2;i<=n;i++){
            res=(res+m)%i;
        }
        return res;
    }
}

编辑于 2024-04-19 16:36:55 回复(0)

Java

牛客839384289号

// 约瑟夫
public int LastRemaining_Solution (int n, int m) {
    // write code here
    ListNode p1=new ListNode(0) ,p2=p1;
    for(int i=1;i<n;i++){
        ListNode node=new ListNode(i);
        p2.next=node;
        p2=p2.next;
    }
    p2.next=p1;
    while(p2.next!=p2){
        for(int i=1;i<m;i++){
            p2=p2.next;
        }
        p2.next=p2.next.next;
    }
    return p2.val;
}

编辑于 2024-03-17 15:54:33 回复(0)

Java

VXTW

逻辑理了半天

import java.util.*;


public class Solution {
    public int LastRemaining_Solution (int n, int m) {
        ArrayList<Integer> arr = new ArrayList<>();
        //初始化
        for (int i = 0; i < n; i++) {
            arr.add(i);
        }

        int p = -1;
        while (arr.size()!=1) {
            if (p>arr.size() - 1) p = arr.size() - 1;
            int temp = p;
            for (int i = temp; i < m + temp; i++) {
                p++;
                if (p>=arr.size()) p=0;
            }
            arr.remove(p--);
        }
        return arr.get(0);
    }
}

编辑于 2024-01-25 16:09:52 回复(0)

Java

梁山教父

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        //使用队列模拟圆圈
        Queue<Integer>queue = new ArrayDeque<>();
        //将所有数字添加到队列
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }
        int num = 1;
        //队列不为空就一直循环
        while (!queue.isEmpty()) {
            //剩下一个那就是幸运儿
            if (queue.size() == 1) {
                return queue.poll();
            }
            //出列的学生，从队列中删除
            if (num == m) {
                queue.poll();
                num = 1;
            //为出列的添加到队列尾部，模拟圆圈
            } else if (num < m) {
                num++;
                int tmp = queue.poll();
                queue.add(tmp);
            }
        }
        return -1;
    }
}

发表于 2023-05-05 19:36:35 回复(0)

Java

不打王者不吃鸡！

import java.util.*;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        
        int i = 0;
        while (list.size() > 1){
            i = (i + m - 1) % list.size();
            list.remove(i);
        }
        
        return list.get(0);
    }
}

发表于 2022-08-30 14:25:13 回复(0)

Java

只会暴力做题

这道题的下标真的是把人整神，感觉挺简单的嗯是修修补补成了丑逼代码。。。

这边选择维护一个list，通过取余判定remove谁，因为游戏是从下一个人开始的，所以还要维护一个pst记录当前游戏起始位置，坑点在边界条件，取余是0的时候要remove的就是上一个元素，特别的1：pst为0的时候上一个元素就是最后一个元素；特别的2：remove元素后，如果pst是最后一个元素，则将它置为0

import java.util.*;
public class Solution {
    public static int LastRemaining_Solution(int n, int m) {
        if (n == 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        int pst = 0;
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        while (list.size() > 1) {
            int size = list.size();
            int temp = m % size;
            if (temp == 0) {
                if (pst == 0) {
                    pst = size - 1;
                } else {
                    pst--;
                }
            } else {
                pst = (pst + temp - 1) % size;
            }
            list.remove(pst);
            if (pst == size - 1) {
                pst = 0;
            }
        }
        return list.get(0);
    }
}

发表于 2022-05-27 21:19:44 回复(0)

Java

不吃速冻饺子

import java.util.*;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
List<Integer> list= new LinkedList();
for (int i = 0; i < n; i++) {
list.add(i);
}
int size=list.size();
int pre=0;
while (size!=1){
pre+=m;
while (pre>size){
pre-=size;
}
if(pre!=0){
pre-=1;
}
list.remove(pre);
size=list.size();
}
return list.get(0);
}
}

发表于 2022-05-20 11:21:21 回复(0)

Java

blue&&lan

why my brain become so slow...QAQ

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        List<Integer> list=new LinkedList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int j=m-1;
        while(list.size()>1){
            while(j>list.size()-1){
                j-=list.size();
            }
            list.remove(j);
            j+=m-1;
        }
        return list.get(0);
    }
}

发表于 2022-05-09 19:40:29 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

没看答案自己憋了一个出来

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        // 解法1：借助队列(ArrayList是有序的)
        ArrayList<Integer> arr = new ArrayList<Integer>();
        // 填满0至n-1的数字
        for(int i=0;i<n;i++){
            arr.add(i);
        }
        // 定义每轮起始位置的指针
        int cur=0;
        // 遍历n-1次，剩下的就是需要找的
        while(n-1>0){
            // 顺延m-1位，计算被选中的索引，取模是怕m > n的情况
            int selected = (cur+m-1)% arr.size();
            // 删除对应索引处的字符
            arr.remove(selected);
            // 更新cur(删除一个字符后，后面的字符自动补齐到selected这里，所以无需+1，再取一次模是怕删除的是最后一个元素)
            cur = selected % arr.size();
            
            n--;
        }
        
        return arr.get(0);
    }
}

发表于 2022-02-02 16:30:38 回复(0)

Java

Monlogue

import java.util.*;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n<=1||m<=0){return -1;}
Queue<Integer> queue=new LinkedList<>();
for (int i = 0; i < n; i++) {
queue.offer(i);
}//存放所有的数字
int temp=1;
while (queue.size()!=1){
//比如走三步，其实小于m就行
for (int i = 0; i < m-1; i++) {
int temp1=queue.poll();
queue.offer(temp1);//把三个数字弹出并插入队尾
}
//此时队列第一个就是要删除掉的值
//queue.remove();//此方法就是获取第一个元素并删除
queue.poll();

}
return queue.remove();
}
}

发表于 2022-01-17 23:06:14 回复(0)

Java

等风来啊a

import java.util.*;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
ArrayList arr=new ArrayList();
for(int i=0;i<n;i++){
arr.add(i);
}
int index=(m-1)%arr.size();
while(arr.size()!=1){
arr.remove(index);
index=(index+m-1)%arr.size();
}
return (int)arr.get(0);
}
}

发表于 2021-12-23 21:14:27 回复(0)

Java

惠灵顿靖

 public static int LastRemaining_Solution(int n, int m) {
        Queue<Integer> queue = new LinkedList<>();
        if (n <= 1 || m == 0) {
            return -1;
        }
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }
        while (queue.size() != 1) {
            for (int i = 0; i < m - 1; i++) {
                queue.add(queue.remove());
            }
            queue.remove();
        }
        return queue.remove();
    }

发表于 2021-10-01 21:56:16 回复(1)

Java

YoungZoo

可用队列来模拟，报完数的到队尾，报到数字m的从队列推出。（这其实这是约瑟夫环问题，但是没必要直接用公式套用这个题目）

public int LastRemaining_Solution(int n, int m) {

if (n <= 0 || m<= 0) return -1;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
queue.offer(i); // 将下标全部进入队列
}
while (queue.size() != 1) { // 只要队列中剩余多余一个元素
int num = 1;
// 模拟报数过程
while (num++ < m) {
queue.offer(queue.poll()); // 都是安全的元素，到队尾即可
}
queue.poll(); // 此时num = m，就要淘汰元素
}
return queue.poll(); // 返回最后一个元素
}

发表于 2021-08-22 10:41:26 回复(0)

Java

^ǒ^月亮船^

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        
        int lastPeople = -1;
        
        if(n <=0 ||m <=0){
            return lastPeople;
        }
        
        int[] arr = new int[n];
        
        int tempM = m;
        
        int i = 0;
        
        while(n != 1){
            while(i < arr.length){
                
                //当只剩一个时，这个人就是最后的人
                if(n == 1){
                    break;
                }
                
                if(arr[i] == 0){
                    if(m == 1){
                        //将选中的置为1
                        arr[i] = 1;
                        //人数减一
                        n--;
                        //重新开始数
                        m = tempM;
                    }else{
                        m--;
                    }
                }
                i++;
            }
            //从头开始
            i = 0;
        }
        
        //寻找最后的一个人
        for(int j = 0 ; j < arr.length ; j++){
            if(arr[j] == 0){
                lastPeople = j;
            }
        }
        
        return lastPeople;
    }
}

发表于 2021-08-16 16:33:15 回复(0)

Java

牛客慧

//借鉴-学习
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        //数学规律：约瑟夫环的问题
        //1.最后剩余的数字下标肯定是0
        //2.往前推，上一轮该数字在环中的下标为:(0+m)%2;
        //3.再往上一轮，下标为:(xx+m)%3
        //......
        if(n==0 && m==0) return -1;
        int id=0;
        for(int i=2;i<=n;i++){
            id=(id+m)%i;
        }
        return id;
    }
}

发表于 2021-08-08 16:59:10 回复(0)

Java

我要offerofferoffer

队列嘛

 public static int LastRemaining_Solution(int n, int m) {
        Queue<Integer> queue = new LinkedList<>();
        if (n <= 1 || m == 0) {
            return -1;
        }
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }
        while (queue.size() != 1) {
            for (int i = 0; i < m - 1; i++) {
                queue.add(queue.remove());
            }
            queue.remove();
        }
        return queue.remove();
    }

发表于 2021-07-21 21:24:02 回复(0)

Java

牛客393046588号

public int LastRemaining_Solution(int n, int m) {
m--;
int x = m;
if (n < 1) {
return -1;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
for (int i = 1; i < n; i++) {
m = m % list.size();
list.remove(m);
m = m + x;
}
return list.get(0);
}

发表于 2021-06-22 14:43:10 回复(0)

Java

牛客771793137号

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n==0) return -1;
        ArrayList<Integer> li=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            li.add(i);
        }
        int num=0;
        int index=0;
        while(li.size()>1){
            if(num<m-1){
                num++;
                if(++index==li.size()) index=0;
            }else{
                li.remove(index);
                if(index==li.size()) index=0;
                num=0;
            }
        }
        return li.get(0);
    }
}

编辑于 2021-06-19 19:37:29 回复(0)

Java

阿尼亚瓦库瓦库

import java.util.ArrayList;

public class Solution {
    
    //简单的约瑟夫环问题啦~~~~
    public int LastRemaining_Solution(int n, int m) {

        if(n == 0) {
            return -1;
        }

        ArrayList<Integer> boys = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            boys.add(i);
        }

        int index = 0;

        while (boys.size()!=1) {

            for (int i = 0; i < m - 1; i++) {
                index = (index + 1)%boys.size();
            }

            boys.remove(index);
        }

        return boys.get(0);
    }
}

发表于 2021-05-02 17:08:33 回复(0)

提交观点

问题信息

基础数学

难度：

130条回答 2805收藏 118378浏览

通过挑战的用户

查看代码

Elastic...

2023-02-13 17:46:26
安布雷拉

2023-02-04 18:54:32
牛客77893...

2022-12-29 13:14:39
牛客74142...

2022-12-24 09:45:33
还在挣扎的螃蟹

2022-12-22 23:43:59

孩子们的游戏(圆圈中最后剩下的数)

输入

输出

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题