华为OD机考算法题：分班

题目部分


题目	分班
难度	易
题目说明	幼儿园两个班的小朋友在排队时混在了一起，每位小朋友都知道自己是否与前面一位小朋友是否同班，请你帮忙把同班的小朋友找出来。小朋友的编号为整数，与前一位小朋友同班用 Y 表示，不同班用 N 表示（第一位小朋友前面没人，用 N 表示）。
输入描述	输入为空格分开的小朋友编号和是否同班标志。比如：6/N 2/Y 3/N 4/Y，表示共4位小朋友，2和6同班，3和2不同班，4和3同班。其中，小朋友总数不超过999，每个小朋友编号大于0，小于等于999。不考虑输入格式错误问题。
输出描述	输出为两行，每一行记录一个班小朋友的编号，编号用空格分开。且： 1、编号需要按照大小升序排列，分班记录中第一个编号小的排在第一行。 2、若只有一个班的小朋友，第二行为空行。 3、若输入不符合要求，则直接输出字符串ERROR。
补充说明	无
------------------------------------------------------
示例
示例1
输入	1/N 2/Y 3/N 4/Y
输出	1 2 3 4
说明	2的同班标记为Y，因此和1同班。 3的同班标记为N，因此和1、2不同班。 4的同班标记为Y，因此和3同班。所以1、2同班，3、4同班，输出为 1 2 3 4

解读与分析

题目解读：

输入为 1 行字符串，每条数据以空格分开。每条数据包含两部分：自己的编号和自己是否与前面的小朋友是否同班（使用 Y 表示同班，N 表示不同班。首位小朋友标记为 N）。

输出 2 行，每行输出一个班的小朋友编号，如果全都在一个班，第二行为空行；每行的数据按照编号从小到大输出；两行数据中，第一个编号最小的数据放在第一行。

分析与思路：

此题需要考虑输入错误的情况，所以此题包含步骤：验证输入，遍历输入数据进行分班，对分班数据排序，输出数据。具体如下：
1. 验证输入。
对输入字符串，以空位为分隔符进行分割，如果无法分割出数据，则输出 ERROR。
逐个遍历分隔后的每条数据，对每条数据，继续以 "/" 进行分割，如果无法分割出数据，则输出 ERROR。对于分割后的数据，如果 "/" 之前的数据不是数字，则输出 ERROR；如果 "/" 之后的数据不是 "Y" 或 "N"，则输出 "N"。首条数据的 "/" 之后为 "N"。
2. 遍历输入数据进行分班。
新建 2 个数组，把第一条数据编号放到第一个数组中，如果第二条数据的 "/" 之后是 "Y"，则放到与前一条数据相同的数组，否则放到第二个数组。
逐条遍历数据，对于每条数据，如果 "/" 是 "Y"，则把这条数据的编号放到与前面一条数据相同的数组中，否则放到另外一条数组中。
3. 对分班数据排序。
对数组中的数据从小到大排序。
4. 输出数据。
如果其中一个数组为空，则输出其中一个数组，另外一个空行。
如果两个数组均不为空，则判断两个数组的第一个元素大小，先输出第一个元素较小的数组。

因涉及到排序，时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

代码实现

Java代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;/*** 篮球比赛* * @since 2023.09.15* @version 0.1* @author Frank**/
public class ClassCheck {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();processClassCheck(input);}}private static void processClassCheck(String input) {String[] kidsInfoStr = input.split(" ");if (kidsInfoStr == null || kidsInfoStr.length == 0) {System.out.println("ERROR");return;}List<Integer>[] classInfo = new ArrayList[2];classInfo[0] = new ArrayList<Integer>();classInfo[1] = new ArrayList<Integer>();int curClass = 1;for (int i = 0; i < kidsInfoStr.length; i++) {String eachRecord = kidsInfoStr[i];String[] recordDetail = eachRecord.split("/");if (recordDetail == null || recordDetail.length != 2) {System.out.println("ERROR");return;}int num;try {num = Integer.parseInt(recordDetail[0]);} catch (NumberFormatException e) {System.out.println("ERROR");return;}if ("Y".equals(recordDetail[1])) {classInfo[curClass].add(num);} else if ("N".equals(recordDetail[1])) {curClass ^= 1;classInfo[curClass].add(num);} else {System.out.println("ERROR");return;}}Collections.sort(classInfo[0]);Collections.sort(classInfo[1]);if (classInfo[1].size() > 0 && classInfo[1].get(0) < classInfo[0].get(0)) {List tmp = classInfo[0];classInfo[0] = classInfo[1];classInfo[1] = tmp;}for (int i = 0; i < classInfo.length; i++) {if (classInfo[i].size() == 0) {// 如果为 0，一定是第二个System.out.println();break;}for (int j = 0; j < classInfo[i].size(); j++) {System.out.print(classInfo[i].get(j));if (j != classInfo[i].size() - 1) {System.out.print(" ");} else {System.out.println();}}}}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {processClassCheck(line);}
}();function processClassCheck(input) {var kidsInfoStr = input.split(" ");if (kidsInfoStr == null || kidsInfoStr.length == 0) {console.log("ERROR");return;}var classInfo = new Array(2);classInfo[0] = new Array();classInfo[1] = new Array();var curClass = 1;for (var i = 0; i < kidsInfoStr.length; i++) {var eachRecord = kidsInfoStr[i];var recordDetail = eachRecord.split("/");if (recordDetail == null || recordDetail.length != 2) {console.log("ERROR");return;}if (isNaN(recordDetail[0]) ) {console.log("ERROR");return;}var num = parseInt(recordDetail[0]);if ("Y" == recordDetail[1]) {classInfo[curClass].push(num);} else if ("N" == recordDetail[1]) {curClass ^= 1;classInfo[curClass].push(num);} else {console.log("ERROR");return;}}var sortFun = function(a,b){return a - b;}classInfo[0].sort( sortFun );classInfo[1].sort( sortFun );if (classInfo[1].length > 0 && classInfo[1][0] < classInfo[0][0]) {var tmp = classInfo[0];classInfo[0] = classInfo[1];classInfo[1] = tmp;}for (var i = 0; i < classInfo.length; i++) {if (classInfo[i].length == 0) {// 如果为 0，一定是第二个console.log("");break;}var output = "";for (var j = 0; j < classInfo[i].length; j++) {output += classInfo[i][j] ;if (j != classInfo[i].length - 1) {output += " ";}}console.log( output );}
}

(完)