九度 oj 1069题解题思路

2019-11-06 07:26:45

字体：大中小

来源：转载

供稿：网友

题目描述：查找学生信息

输入N个学生的信息，然后进行查询。

输入：

输入的第一行为N，即学生的个数(N<=1000)接下来的N行包括N个学生的信息，信息格式如下：01 李江男 2102 刘唐男 2303 张军男 1904 王娜女 19然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下：02030104

输出：

输出M行，每行包括一个对应于查询的学生的信息。如果没有对应的学生信息，则输出“No Answer!”

样例输入：

401 李江男 2102 刘唐男 2303 张军男 1904 王娜女 1950203010403

样例输出：

02 刘唐男 2303 张军男 1901 李江男 2104 王娜女 1903 张军男 19

来源： 2003年清华大学计算机研究生机试真题

解决思路一：

1.将输入的学生数据保存在数组中2.遍历数组，根据输入的学号查找数组中的学生信息，并输出

但是此方法在于时间复杂度过高O(N*M)，达到千万数量级，可能发生超时。

代码示例

import java.util.Scanner;class Student{ // 定义学生信息 public String id; PRivate String name; private String sex; private int age; public Student(String id, String name, String sex, int age){ this.id = id; this.name = name; this.sex = sex; this.age = age; } public String toString(){ return this.id + " " + this.name + " " + this.sex + " " + this.age; }}public class Main{ public static void main(String [] args){ Scanner cin = new Scanner(System.in); Student [] data = new Student[1001]; while(cin.hasNext()){ int N = cin.nextInt(); // 存储输入的全部学生数据 for(int i = 0; i < N; i++){ data[i] = new Student(cin.next(), cin.next(), cin.next(), cin.nextInt()); } int M = cin.nextInt(); // 在存储全部学生数据的数组中根据输入的学号查找对应学生信息 for(int j = 0; j < M; j++){ String str = cin.next(); int k = 0; for(k = 0; k < N; k++){ // 找到学生数据，则输出 if(data[k].id.equals(str)){ System.out.println(data[k]); break; } } // 未找到对应的学生数据 if(k == N){ System.out.println("No Answer!"); } } } }}

解决思路二：

在思路一中使用遍历数组查找的时间复杂度较高。要降低查找所花费的时间，可以使用二分查找。但是要使用二分查找的前提需要将学生信息数组按照学号进行排序。所以思路二可以总结如下： 1.将输入的学生数据保存在数组中,并按照学号进行排序。 2.使用输入要查找的学号对学生信息数组进行二分查找，并打印信息。

此时的时间复杂度为：O( nlog2n $n{log_2}n$ (排序) + mlog2n $m{log_2}n$ (查找) )

代码示例

import java.util.Arrays;import java.util.Scanner;class Student implements Comparable<Student1>{ // 学生的基本信息 private String id; private String name; private String sex; private int age; public Student(String id, String name, String sex, int age){ this.id = id; this.name = name; this.sex = sex; this.age = age; } public String toString(){ return this.id + " " + this.name + " " + this.sex + " " + this.age; } // 由于要使用Arrays.sort()方法，需要指定比较标准 public int compareTo(Student stu){ return this.id.compareTo(stu.id); }}public class Main{ public static void main(String [] args){ Scanner cin = new Scanner(System.in); int N = cin.nextInt(); // 使用数组存储全部输入的学生信息 Student [] data = new Student [N]; for(int i = 0; i < N; i++){ data[i] = new Student(cin.next(), cin.next(), cin.next(), cin.nextInt()); } // 对学生信息数组按照学号进行排序 Arrays.sort(data); int M = cin.nextInt(); for(int j = 0; j < M; j++){ // 以输入查找的学号为参数对学生数组进行二分查找 int x = search(data, new Student(cin.next(), null, null, 0)); // 找到数据 if(x != -1){ System.out.println(data[x]); } // 未找到数据 else{ System.out.println("No Answer!"); } } } // 二分查找 public static int search( Student [] data, Student x){ int base = 0; int top = data.length - 1; int mid = top / 2; while(top >= base){ if((x.compareTo(data[mid]) > 0)){ base = mid + 1; mid = (base + top) / 2; } else if(x.compareTo(data[mid]) < 0){ top = mid - 1; mid = (base + top) / 2; } else{ return mid; } } return -1; }}

注意： $/color{red}{注意：}$ 要使用Arrays.sort()方法对自定义类对象数组进行排序，自定义类要实现Comparable接口,并覆写Comparable接口中的compareTo()方法指定比较排序规则 $/color{blue}{自定义类要实现Comparable接口,并覆写Comparable接口中的compareTo()方法指定比较排序规则}$

解决思路三：

以上两种思路，都是将输入的学生数据顺序存储在数组中，在根据输入学号从数组中查找。下面通过Hash的简单应用，完成查找功能。简要思路如下：1.将输入的学生信息中的学号转换成整数，再以该整数为数组索引存储2.根据输入的学号转成整数，以该整数为索引直接从数组中读出查找的学生信息。

代码实现

import java.util.Scanner;class Student{ // 学生基本信息 private String id; private String name; private String sex; private int age; public Student(String id, String name, String sex, int age){ this.id = id; this.name = name; this.sex = sex; this.age = age; } public String toString(){ return this.id + " " + this.name + " " + this.sex + " " + this.age; }}public class Main{ public static void main(String [] args){ Scanner cin = new Scanner(System.in); while(cin.hasNext()){ int N = cin.nextInt(); Student [] data = new Student[N + 1]; // 存储学生数据 for(int i = 0; i < N; i++){ String str = cin.next(); // 将学号转成整数后，以该整数为索引存储学生数据信息 data[transform(str)] = new Student(str, cin.next(), cin.next(), cin.nextInt()); } int M = cin.nextInt(); for(int i = 0; i < M; i++){ // 查找学号对应的整数 int temp = transform(cin.next()); if(data[temp] != null){ System.out.println(data[temp]); } else{ System.out.println("No Answer!"); } } } } // 将字符串类型的学号转换成整数 public static int transform(String str){ if(str.toCharArray()[0] == '0'){ str = str.substring(1, str.length()); } return Integer.parseInt(str); }}

解决思路四：

由于题目可以简单理解为使用一个值去查找另一个值，所以可以想到使用Map集合框架来完成。思路如下：1.将学生数据以学号为key,对应数据为value存储在HashMap集合中2.使用要查找的学生学号为key，查找对应的学生数据value

代码示例

import java.util.Scanner;import java.util.Map;import java.util.HashMap;class Student{ // 基本学生信息 private String id; private String name; private String sex; private int age; public Student(String id, String name, String sex, int age){ this.id = id; this.name = name; this.sex = sex; this.age = age; } public String toString(){ return this.id + " " + this.name + " " + this.sex + " " + this.age; }}public class Main{ public static void main(String [] args){ Scanner cin = new Scanner(System.in); // 以学号为键值，学生对象为map值 Map<String, Student> map = new HashMap<String, Student>(); while(cin.hasNext()){ int N = cin.nextInt(); for(int i = 0; i < N; i++){ String str = cin.next(); // 学生数据加入map集合中 map.put(str, new Student(str, cin.next(), cin.next(), cin.nextInt())); } int M = cin.nextInt(); for(int j = 0; j < M; j++){ // 以查找学号为键值，查找对应的map值 Student stu = map.get(cin.next()); if(stu != null){ System.out.println(stu); } else{ System.out.println("No Answer!"); } } // 清空集合 map.clear(); } }}

注意 $/color{red}{注意}$ :以上只是本人的一些想法实现，不知何原因在本地测试数据可以得到正确结果，但在提交到九度oj上并未能AC，非常想知道问题在何处，如果各位知道原因，非常欢迎指出。

上一篇：汉诺塔的递归实现与非递归实现

下一篇：最短路（Dijstra算法）