首页 > 试题广场 >

报数

[编程题]报数
  • 热度指数：3113 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
今年7月份vivo迎来了新入职的大学生，现在需要为每个新同事分配一个工号。人力资源部同事小v设计了一个方法为每个人进行排序并分配最终的工号，具体规则是：
将N（N<10000）个人排成一排，从第1个人开始报数；如果报数是M的倍数就出列，报到队尾后则回到队头继续报，直到所有人都出列；
最后按照出列顺序为每个人依次分配工号。请你使用自己擅长的编程语言帮助小v实现此方法。


输入描述:
输入2个正整数，空格分隔，第一个代表人数N，第二个代表M：


输出描述:
输出一个int数组，每个数据表示原来在队列中的位置用空格隔开，表示出列顺序：
示例1

输入

6 3

输出

3 6 4 2 5 1

说明

6个人排成一排，原始位置编号即为1-6。最终输出3 6 4 2 5 1表示的是原来编号为3的第一个出列，编号为1的最后一个出列。
算法知识视频讲解
添加回答
C/C++
道可道非常道嘤头像 道可道非常道嘤
挺简单的，建议背诵
思路：抽到谁谁出列，删掉这个数，M的倍数==》每隔M-1个就抽一个，i从0开始抽，抽到最后一个接着从头开始算就是i=i%v.size();直到都抽完了就结束了。
  
void solution(int N, int M)
{
    if (N <1||M<1)return;
    vector<int> v(N);
    for (int i = 0; i<N; i++)v[i] = i + 1;
    int i = 0;
    while (v.size()>0) {
        i += M-1;
        if (i>=v.size())i = i%v.size();
        cout << v[i] << " ";
        v.erase(i + v.begin());
    }
    cout << endl;
}


编辑于 2020-03-07 18:40:16 回复(5)
森海北屿丶头像 森海北屿丶 
void solution(int N, int M)
{
    //构造环形链表
    _node* head = new _node;
    head->num = 1;
    _node* pre = head;
    for(int i = 2;i <= N;i++){
        _node* temp = new _node;
        temp->num = i;
        pre->next = temp;
        pre = pre->next;
    }
    pre->next = head;
    //当M=1时，按顺序输出即可
    if(M == 1){
        for(int i = 0; i < N - 1;i++){
            cout << head->num<< " ";
            head = head->next;
        }
        cout << head->num;
        return;
    }
    //当M>1时
    while(head != NULL){
        //找到要输出的节点的前一个节点
        for(int i = 0;i < M - 2;i++){
            head = head->next;
        }
        //输出当前节点下一个节点的元素
        cout << head->next->num << " ";
        //判断输出完后链表中是否只剩下了一个节点
        if(head == head->next->next){
            cout << head->num;
            return;
        }
        //从链表中删除输出的节点，将当前节点的下一个节点指向删除的节点的下一个节点
        head->next = head->next->next;
        head = head->next;
    }
}

发表于 2020-06-06 12:25:04 回复(0)
SugarChl头像 SugarChl 
x = input()
N = int(x.split()[0])
M = int(x.split()[1])
p = [i + 1 for i in range(N)]
count = 1
index = 0
while len(p) > 0:
 
    if index >= len(p):
        index = index % len(p)
    if count % M == 0:
        print(p[index], end=" ")
        p[index] = 0
        p.remove(p[index])
        count += 1
        continue
 
    count += 1
    index += 1

发表于 2020-02-03 22:08:20 回复(1)
xhjiang头像 xhjiang
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct A
{
    int val;
    int count;
};

int main()
{
    int N, M;
    cin >> N >> M;
    vector<A> ivec;
    for (int i = 1; i <= N; i++)
    {
        A a;
        a.val = i;
        a.count = 0;
        ivec.push_back(a);
    }
    int count = 0;
    while (ivec.size() > 1)
    {
        for(int i=0;i<ivec.size();i++)
        {
            count++;
            ivec[i].count=count;
            if ((ivec[i].count) % M == 0)
            {
                cout << ivec[i].val << " ";
                ivec.erase(ivec.begin() + i);
                i--;
            }
        }
    }
    cout << ivec[0].val << endl;

    return 0;

}
简单的约瑟夫环问题，注意其中设置一个永远增长的量count，还有自身的值，所以要用到结构体，存自身的值value和排队数数的值count
进入循环前，初始化时veic【i】count都设置为0。在后面的每次循环中，veic[i] count++，如果veic[i] count%M ==0就把这个i这个数给灭掉，即veic.erase(veic.begin()+i)意思是消除第i个元素，然后i- -，因为要把后面一个数会立马填充上来，填充掉这个位置。一直循环直到这个i=veic.size()时候停止
发表于 2019-11-13 23:25:02 回复(0)
pein531头像 pein531
直接用ArrayList进行模拟，如果报数为m的倍数就从ArrayList中将此元素进行移除 
import java.io.*;
import java.util.ArrayList;

/**
 * Welcome to vivo !
 */

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int input[] = parseInts(inputStr.split(" "));
        String output = solution(input);
        System.out.println(output);
    }

    private static int[] parseInts(String[] strArr) {
        if (strArr == null || strArr.length == 0) {
            return new int[0];
        }
        int[] intArr = new int[strArr.length];
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        return intArr;
    }

    private static String solution(int[] input) {
        // TODO Write your code here
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < input[0]; i++)
            list.add(i + 1);
        int start = 1, pos = 0;
        while(list.size() > 0){
            if(start % input[1] == 0){
                // pos位置的员工报到了m的倍数，出列
                sb.append(list.remove(pos) + " ");
            }else{
                // 否则不出列，位置继续后移
                pos ++;
            }
            // 到队尾后回到队首
            if(pos >= list.size())
                pos -= list.size();
            // 报数
            start ++;
        }
        return sb.toString().trim();
    }

}


编辑于 2021-02-09 17:29:31 回复(1)
JavaScript
勇敢牛牛不怕困难j头像 勇敢牛牛不怕困难j
好像没有js写的 
function solution(n, m) {
    let v = new Array(n+1);
    let res = [];
    for(let i=0;i<n;i++){
        v[i] = i+1;
    }
    let j = 0;
    while(v.length>0){
        j += m-1;
        if(j>=v.length) j = j%v.length;
        res.push(v[j]);
        v.splice(j,1);
    }
    let result = '';
    for(let i=0;i<res.length;i++){
        result += res[i]+' ';
    }
    return result;
}
while (line = readline()) {
    var params = line.split(" ");
    var n = params[0];
    var m = params[1];
    print(solution(n, m));
}


发表于 2021-01-02 20:22:39 回复(0)
Python
青春逐梦ty头像 青春逐梦ty 
def solution(N,M):
    
    li = list(map(int, range(1, N + 1)))
    sub = li
    k = 0
    while sub:
        li = []
        for i in range(len(sub)):
            k += 1
            if k % M == 0:
                print(sub[i], end=' ')  # 满足条件就输出
            else:
                li.append(sub[i])  # 不满足就加进新的列表
        sub = li  # 最后将新的列表赋值，再进行循环
    pass

N,M = [int(i) for i in input().split()]
solution(N,M)

发表于 2020-12-09 16:37:15 回复(0)
Python
朝夕_头像 朝夕_ 
def solution(N,M):
    if N < 1&nbs***bsp;M < 1:
        return 
    a = [i for i in range(1,N+1)]
    count = 1
    res = []
    while a:
        temp = []
        for i in a:
            if count%M != 0:
                temp.append(i)
            else:
                res.append(i)
            count += 1
        a = temp
    print(" ".join(map(str,res)))
    return
N,M = [int(i) for i in input().split()]
solution(N,M)

发表于 2020-03-07 15:15:21 回复(0)
后知后觉的Jim头像 后知后觉的Jim

1.选择数据结构方面，用List集合可以了，值得注意的是当有人出队时，后一个元素会前移代替当前元素的位置
2.做了两轮处理，将员工1~N放入List的时候就先报数一轮；第二轮将剩余的人出队

     private static String solution(int[] input) {
        //队列初始化+初次编号
        List<Integer> employee=new ArrayList<Integer>();
        employee.add(-2);//虚拟头结点填充，因为是从1开始报数 
        StringBuilder res=new StringBuilder();//输出
        int N=input[0];//input[0]=N人数
        int M=input[1];//倍数
        int i=1;
        while(i<=N){
            if(i%M==0){
                res.append(i).append(" ");//输出要求有空格
            }else{
                employee.add(i);
            }
            i++;
        }
        int count=N+1;//报了一轮数之后该有的值
        //二次编号
        while(true){
            i=1;//从头开始重新报数
            int len=employee.size();
            if(len==1){//只剩下虚拟头结点时
                break;
            }
            while(i<len){//i是数组的下标
                if(count%M==0){
                    res.append(employee.get(i)).append(" ");//拿到该下标 i 对应的value
                    employee.remove(i);//从队列删除该下标i对应的值
                    len=employee.size();//删除之后后面的结点会补上原来的位置，但是len缩短了
                    count++;// 前一个人报数并出队后，后一个人代替了它的位置并报数+1（该处比较特殊） 
                    continue;//下标指针i仍然停止当前位置(因为后面的数值往前移动了)
                }
                i++;
                count++;
            }        
        }
        return res.toString();
    }
发表于 2020-03-01 17:02:46 回复(0)
C/C++
卷毛侠头像 卷毛侠
void solution(int N, int M)
{
    // TODO Write your code here 
    queue<int> q;
    int i = 0;
    int j = 0;
    while(i++ < N)
        q.push(i);
    while(q.size() != 0){
        j++;
        int tmp = q.front();
        if(j % M == 0){
            if(q.size() != 1)
                cout<<tmp<<" ";
            else
                cout<<tmp<<endl;
            q.pop();
            j = 0;
        }
        else{
            q.pop();
            q.push(tmp);
        }
    }
}
发表于 2019-12-21 14:11:04 回复(0)
巨人的肩膀头像 巨人的肩膀
环形链表模拟这个过程即可 
struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(NULL) {};
};
 
void solution(int N, int M)
{
    Node* head = new Node(1);
    Node* curr = head;
    for (int i = 2; i <= N; ++i) {
        curr->next = new Node(i);
        curr = curr->next;
    }
    curr->next = head;
    Node* prev = curr;
    curr = head;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j < M; ++j) {
            prev = curr;
            curr = curr->next;
        }
        cout << (curr->val) << " ";
        prev->next = curr->next;
        curr = curr->next;
    }
}


发表于 2019-11-20 22:24:09 回复(0)
牛客895101630号头像 牛客895101630号 
一个简单不易错的方法。
其他人的方法有些使用 erase 或者 remove 的操作删除元素，这个操作的复杂度是O(n)，使用队列可降到Ｏ(1).

def solution(N,M):
    from collections import deque
    que = deque(list(range(1,N+1)))
    i = 0
    while que:
        i += 1
        if i%M == 0: # 如果是M的倍数，移出队列并打印
            print(que.popleft() ,end = " ")
        else: # 否则把队首放到队尾
            que.append(que.popleft())
         
N,M = [int(i) for i in input().split()]
solution(N,M)

编辑于 2020-06-06 01:26:10 回复(2)
cheng_fourier头像 cheng_fourier 
C语言写的，想法是将人数编号放进一个数组，然后在循环里遍历数组，
check到第M个人就把他的编号打印，并把数组里他的编号置零，当遍历到数组尾部时初始化下标
继续从1号开始。每次遍历都if判断编号是否为0，为0就跳过不计入check。最后是每打印一个编号
就count+1，在打印完所有人后判断count的值跳出循环

void solution(int N, int M){

    // TODO Write your code here
    int member[N];
    for(int i = 1; i <= N; i++)
    {
        member[i-1] = i;
    }
    int check = 0;
    int count = 0;
    for(int i = 1; i <= N; i++)
    {
        if(count == N) break;
        if(member[i-1] != 0){
            check++;
            if(check == M){
                printf("%d ", member[i-1]);
                count++;
                member[i-1] = 0;
                check = 0;
            }
        }
        if(i == N)  i = 0;
    }
}


发表于 2023-02-28 14:16:09 回复(0)
牛客772922196号头像 牛客772922196号 
function solution(n, m) {
    let person = {};
    for (let i = 1; i <= n; i++) {
        person[i] = i;
    }
    let res = [];
    while (res.length !== n) {
        // 找到此时最末尾的数值
        let max = Math.max(...Object.values(person));
        // 还有多少人没有出去
        // 遍历查找谁符合要求
        for (let item in person) {
            if (person[item] % m === 0) {
                res.push(Number(item));
                delete person[item]; // 移除队列
            }
        }
        for (let item in person) {
            person[item] = max + 1;
            max++;
        }
    }
    return res;
}

发表于 2021-03-10 14:58:13 回复(0)
Python
ΔtZ.头像 ΔtZ. 
n,m = map(int,input().split())
p = [i+1 for i in range(n)] 
count,idx = 1,0
while p:
    idx %= len(p)
    if count%m ==0:
        print(p[idx],end=' ')
        p.remove(p[idx])
        count +=1
        continue
    count +=1
    idx +=1

发表于 2020-08-12 12:04:01 回复(0)
Java
imleep头像 imleep
本题目其实为约瑟夫环。具体代码如下。 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int key = sc.nextInt();
        sc.close();
        int[] orderNo = getOrderNo(n, key);
        String s = "";
        for (int i = 0; i < orderNo.length; i++) {
            s += orderNo[i] + " ";
        }
        System.out.println(s);
    }

    public static int[] getOrderNo(int n, int key) {
        List<Integer> list = new ArrayList<>(n); // 构建链表
        for (int i = 0; i < n; i++) list.add(i + 1);
        int[] order = new int[n]; // 构建输出序列
        int next = 0; // 指针的下一个位置
        int count = 0; // 报数
        int flag = 0; // 输出序列的下标
        while (list.size() != 0) {
            count++;
            if (count % key == 0) {
                Integer remove = list.remove(next);
                order[flag++] = remove.intValue();
            } else {
                next = (next + 1) % list.size();
            }
        }
        return order;
    }
}


发表于 2020-06-11 10:21:50 回复(0)
305602188头像 305602188
约瑟夫问题，使用单循环链表来解决 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int input[] = parseInts(inputStr.split(" "));
        String output = solution(input);
        System.out.println(output);
    }
 
    private static int[] parseInts(String[] strArr) {
        if (strArr == null || strArr.length == 0) {
            return new int[0];
        }
        int[] intArr = new int[strArr.length];
        for (int i = 0; i < intArr.length; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }
        return intArr;
    }
 
    private static String solution(int[] input) {
 
        // TODO Write your code here
        SingleCirList list = new SingleCirList();
        list.add(input[0]);
        list.countStu(1,input[1]);
        return list.res.toString();
    }
}
 
//创建一个单循环链表
class SingleCirList{
    //创建一个first节点，当前没有编号
    Sdu first = null;
    StringBuffer res = new StringBuffer();
     
    //添加学生结点构成一个单链表
    public void add(int nums){
        // 生成辅助结点
        Sdu curSdu = null;
        //添加学生结点，构成环形链表
        for(int i=1; i<= nums; i++){
            Sdu sdu = new Sdu(i); //生成一个结点
            if(i == 1){//这个判断很重要
                first = sdu;
                first.next = first;
                curSdu = first;
            }
            curSdu.next = sdu;
            sdu.next =first;
            curSdu = sdu;
        }
    }
     
    public void countStu(int start, int countNum){
        //创建辅助结点
        Sdu helper = first;
        while(helper.next != first){
            helper = helper.next;
        }
        for(int i=0; i< start-1; i++){
            first = first.next;
            helper = helper.next;
        }
        while(helper != first){
            for(int i=1; i<=countNum-1; i++){
                first = first.next;
                helper = helper.next;
            }
            res.append(first.no+" ");
            first = first.next;
            helper.next = first;
        }
        res.append(first.no+" ");
    }
}
 
// 学生结点
class Sdu{
    int no;
    Sdu next;
    public Sdu(int no){
        this.no = no;
    }
}



发表于 2020-06-07 10:17:17 回复(0)
即将成为内推官头像 即将成为内推官
人作为数组的下标，其不断变化的编号作为数组的值。就这个输出搞了老半天。 
private static String solution(int[] input) {
 
        // TODO Write your code here
        int n = input[0], m = input[1], nums = 0, end = n+1;
        int[] stud = new int[n];
       
        StringBuilder s = new StringBuilder();
        for(int i = 0; i < n; i++){
            stud[i] = i+1;
        }
        while(nums < n){
            for(int i = 0; i < n; i++){
                if (stud[i] > 0){
                    if (stud[i] % m == 0){
                        s.append(i+1).append(" ");
                        nums++;
                        stud[i] = -1;
                    }else {
                        stud[i] = end++;
                    }
                     
                }
            }
             
        }
        
       s.deleteCharAt(s.length() -1);
        return s.toString();
 }



发表于 2020-06-06 17:15:30 回复(0)
坚持挣扎头像 坚持挣扎
Java版 基于道可道非常道嘤 
private static String solution(int[] input) {

        // TODO Write your code here
        int N = input[0];
        int M = input[1];
        if(N<1 || M<1) return null;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++) arr.add(i+1);
        int i=0;
        while(arr.size()>0){
            i += M-1;
            if(i>=arr.size()) i=i%arr.size();
            sb.append(arr.get(i)).append(" ");
            arr.remove(i);
        }
        return sb.delete(sb.length()-1,sb.length()).toString();
}

发表于 2020-06-01 09:03:55 回复(0)
平成最后的无业游民头像 平成最后的无业游民
n,m=list(map(int,input().split(" ")))
i=0
j=1
arr=list(range(1,n+1))
t=[]
while len(arr)!=0:
    if j%m ==0:
        t=t+[arr[i]]
        arr.pop(i)
        i=i-1
    i=i+1
    j=j+1
    if i>=len(arr):
        i=i-len(arr)
print(" ".join(list(map(str,t))))
发表于 2020-03-07 20:07:26 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 数据挖掘工程师 测试开发工程师 vivo 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
23条回答 8068浏览

热门推荐

通过挑战的用户

相关试题

报数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号