报数

[编程题]报数

热度指数：3116 时间限制：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的最后一个出列。

算法知识视频讲解

Java

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)