(C卷,100分)- 约瑟夫问题（Java & JS & Python & C）

题目描述

输入一个由随机数组成的数列（数列中每个数均是大于 0 的整数，长度已知），和初始计数值 m。

从数列首位置开始计数，计数到 m 后，将数列该位置数值替换计数值 m，

并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止。

如果计数到达数列尾段，则返回数列首位置继续计数。

请编程实现上述计数过程，同时输出数值出列的顺序。

比如：输入的随机数列为：3,1,2,4，初始计数值 m=7，从数列首位置开始计数（数值 3 所在位置）

第一轮计数出列数字为 2，计数值更新 m=2，出列后数列为 3,1,4，从数值 4 所在位置从新开始计数

第二轮计数出列数字为 3，计数值更新 m=3，出列后数列为 1,4，从数值 1 所在位置开始计数

第三轮计数出列数字为 1，计数值更新 m=1，出列后数列为 4，从数值 4 所在位置开始计数

最后一轮计数出列数字为 4，计数过程完成。输出数值出列顺序为：2,3,1,4。

要求实现函数：

void array_iterate(int len, int input_array[], int m, int output_array[])

输入描述

 int len：输入数列的长度； int intput_array[]：输入的初始数列 int m：初始计数值

输出描述

 int output_array[]：输出的数值出列顺序

用例

题目解析

本题就是约瑟夫环的变种题。

约瑟夫环的解题有多种方式，比较容易理解和实现的可以使用双端队列。

即intput_array当成双端队列，从队头取出元素，判断此时计数是否为m：

• 若是，则将取出的元素加入output_arr，并将取出的元素的值赋值给m，然后len–，计数重置为1
• 若不是，则将取出的元素塞回intput_array的队尾，仅计数++

但是本题JS是基于数组实现的双端队列，因此每次头部元素出队，都意味着一次O(n)复杂度的数组元素前移一位操作，这是非常影响性能的。

对于Java，Python都有内置的双端队列结构，因此可以直接复用，对于C，可以自己实现双端队列结构。

因此JS语言我们可以选择循环链表来模拟约瑟夫环。

循环链表本身就实现了环形结构，其head.prev = tail，tail.next = head。

且循环链表删除节点的复杂度是O(1)。

唯一的遗憾是，JS没有原生的循环链表结构，我们需要自己实现。但是我们只需要实现最简单的循环链表即可，即只实现循环链表的尾部新增节点操作即可。而删除操作可以在实际业务中完成。

JavaScript算法源码

双端队列

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    const input_arr = lines[0].split(",");
    const len = lines[1];
    const m = lines[2];

    const output_arr = [];
    array_iterate(len, input_arr, m, output_arr);
    console.log(output_arr.join(","));
    lines.length = 0;
  }
});

function array_iterate(len, input_arr, m, output_arr) {
  let i = 1;
  while (len > 0) {
    const out = input_arr.shift();
    if (i == m) {
      output_arr.push(out);
      m = out;
      i = 1;
      len--;
    } else {
      input_arr.push(out);
      i++;
    }
  }
}

循环链表

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    const input_arr = lines[0].split(",");
    const len = lines[1];
    const m = lines[2];

    const output_arr = [];
    array_iterate(len, input_arr, m, output_arr);
    console.log(output_arr.join(","));
    lines.length = 0;
  }
});

function array_iterate(len, input_arr, m, output_arr) {
  const cll = new CircularLinkedList();
  cll.init(input_arr);

  let cur = cll.head;
  let i = 1;
  while (cll.size) {
    if (i == m) {
      const pre = cur.prev;
      const nxt = cur.next;

      pre.next = nxt;
      nxt.prev = pre;

      m = cur.val;
      output_arr.push(m);
      cur.next = cur.prev = null;

      cur = nxt;

      i = 1;
      cll.size--;
    } else {
      i++;
      cur = cur.next;
    }
  }
}

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(val) {
    const node = new Node(val);

    if (this.size) {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    } else {
      this.head = node;
      this.tail = node;
    }

    this.head.prev = this.tail;
    this.tail.next = this.head;

    this.size++;
  }

  init(arr) {
    arr.forEach((val) => {
      this.append(val);
    });
  }
}

Java算法源码

Java可以使用LinkedList模拟双端队列

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    Integer[] input_arr =
        Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);

    int len = Integer.parseInt(sc.nextLine());

    int m = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(input_arr, len, m));
  }

  public static String getResult(Integer[] input_arr, int len, int m) {
    LinkedList<Integer> dq = new LinkedList<>(Arrays.asList(input_arr));

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

    int i = 1;
    while (len > 0) {
      Integer out = dq.removeFirst();

      if (i == m) {
        output_arr.add(out);
        m = out;
        i = 1;
        len--;
      } else {
        dq.add(out);
        i++;
      }
    }

    StringJoiner sj = new StringJoiner(",");
    for (Integer ele : output_arr) {
      sj.add(ele + "");
    }
    return sj.toString();
  }
}

Python算法源码

from collections import deque

# 输入获取
input_arr = deque(list(map(int, input().split(","))))
length = int(input())
m = int(input())


# 算法入口
def getResult():
    global input_arr
    global length
    global m

    output_arr = []

    i = 1
    while length > 0:
        out = input_arr.popleft()
        if i == m:
            output_arr.append(out)
            m = out
            i = 1
            length -= 1
        else:
            input_arr.append(out)
            i += 1

    return ",".join(map(str, output_arr))


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode {
    int ele;
    struct ListNode* next;
} ListNode;

typedef struct {
    int size;
    ListNode* head;
    ListNode* tail;
} LinkedList;

LinkedList* new_LinkedList();
void addLast_LinkedList(LinkedList* link, int ele);
int removeFirst(LinkedList* link);

int main() {
    LinkedList* dq = new_LinkedList();

    int num;
    while(scanf("%d", &num)) {
        addLast_LinkedList(dq,num);
        if(getchar() != ',') break;
    }

    int len;
    scanf("%d", &len);

    int m;
    scanf("%d", &m);

    LinkedList* output_arr = new_LinkedList();

    int i = 1;
    while(len > 0) {
        int out = removeFirst(dq);

        if(i == m) {
            addLast_LinkedList(output_arr,out);
            m = out;
            i = 1;
            len--;
        } else {
            addLast_LinkedList(dq,out);
            i++;
        }
    }

    char res[100000];

    ListNode* cur = output_arr->head;
    while(cur != NULL) {
        char tmp[10];
        sprintf(tmp, "%d", cur->ele);
        strcat(res, tmp);

        cur = cur->next;

        if(cur != NULL) {
            strcat(res, ",");
        }
    }

    puts(res);

    return 0;
}

LinkedList* new_LinkedList() {
    LinkedList* link = (LinkedList*) malloc(sizeof(LinkedList));

    link->size = 0;
    link->head = NULL;
    link->tail = NULL;

    return link;
}

void addLast_LinkedList(LinkedList* link, int ele) {
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));

    node->ele = ele;
    node->next = NULL;

    if(link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

int removeFirst(LinkedList* link) {
    if(link->size == 0) exit(-1);

    ListNode* removed = link->head;

    if(link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}