第三次CCF计算机软件能力认证题目一：图书馆读者访问记录

问题

【问题描述】

小明最近当上了图书馆管理员&＃xff0c;请帮助小明实现这样一个程序&＃xff1a;小明按先后顺序输入一串访问图书馆的读者编号序列&＃xff0c;程序输出该读者当前第几次访问图书馆。

【输入格式】

第一行输入正整数N&＃xff0c;表示接下来有N个读者访问记录。

第二行输入N个访问记录的读者编号&＃xff08;正整数&＃xff09;&＃xff0c;用空格隔开。

【输出格式】

输出一行&＃xff0c;表示读者是第几次访问图书馆&＃xff0c;用空格隔开。

【输入样例】

5

1 2 1 3 1

【输出样例】

1 1 2 1 3 

分析

这题是本次考试的第一题&＃xff0c;难度不大&＃xff0c;热下身。看了输入样例、输出样例后&＃xff0c;不难发现&＃xff0c;程序需要求出的是某个数字当前出现过的次数。

法一

可以考虑用一个嵌套循环解决&＃xff1a;

设数组为data[N]

1. 从data中位置 i &＃xff08;0<&＃61;i

2. 从数组的位置0处开始到 i&＃xff0c;对每一个 j (0<&＃61;j<&＃61;i)若有data[j] &＃61;&＃61; data[i]&＃xff0c;则count&＃43;&＃43;.

  循环代码&＃xff1a;

for(int i &＃61; 0; i < N; i&＃43;&＃43;){int count &＃61; 0; //记数器for(int j &＃61; 0; j <&＃61; i; j&＃43;&＃43;){if(data[i] &＃61;&＃61; data[j]){count&＃43;&＃43;;}}result &＃43;&＃61; count &＃43; " ";
}

问题解决。

法二

可是&＃xff0c;如果数据量比较大&＃xff0c;用嵌套循环的效率似乎不是很好。

第二种方法可以只使用一个循环解决&＃xff0c;牺牲空间换取时间。O(n).

这种方法需要引入LinkedList&＃xff0c;HashMap这些java.util包下的数据结构&＃xff08;看了一下CCF CSP考试说明&＃xff0c;应试者的数据结构、分支语句、循环语句等等基本功是其主要考查的目的之一&＃xff09;。LinkedList用来存储读者的编号&＃xff0c;而HashMap则以编号为键&＃xff08;Key&＃xff09;&＃xff0c;以读者访问次数&＃xff08;数字出现次数&＃xff09;为值&＃xff08;Value&＃xff09;&＃xff0c;将这些重要存储起来。

思路大致如此&＃xff1a;

1. 在LinkedList中取出读者编号id

2. 判断HashMap中是否有id做键&＃xff0c;若有则将次数&＃43;1覆盖回HashMap&＃xff0c;无则将id作为键&＃xff0c;1作为值 put到HashMap里

String result &＃61; "";
//引入一个Map来存储数字出现的次数&＃xff0c;Key为读者编号&＃xff0c;Value为访问的次数
Map map &＃61; new HashMap();for(int i &＃61; 0; i < data.size(); i&＃43;&＃43;){int id &＃61; data.get(i);     //得到一个读者的编号Integer count &＃61; map.get(id);    //从map中读取次数if(count &＃61;&＃61; null){ //若读取到的为null&＃xff0c;则说明之前没有访问过result &＃43;&＃61; 1 &＃43; " ";map.put(id, 1); //往map中添加put的次数}else{ //若之前有访问过count&＃43;&＃43;; //访问次数&＃43;1map.put(id, count); //将&＃43;1后的数据覆盖原来的访问次数result &＃43;&＃61; count &＃43; " ";}
}

代码

以下为完整代码&＃xff1a;

法一

import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}public void run(){//读取小明输入的记录个数&＃xff0c;并创建相应大小的数组Scanner scanner &＃61; new Scanner(System.in);final int N &＃61; scanner.nextInt();//创建记录数组int[] data &＃61; new int[N];//读取N次访问记录for(int i &＃61; 0; i < N; i&＃43;&＃43;){data[i] &＃61; scanner.nextInt();}//处理String result &＃61; "";for(int i &＃61; 0; i < N; i&＃43;&＃43;){int count &＃61; 0; //记数器for(int j &＃61; 0; j <&＃61; i; j&＃43;&＃43;){if(data[i] &＃61;&＃61; data[j]){count&＃43;&＃43;;}}result &＃43;&＃61; count &＃43; " ";} System.out.println(result); //输出结果}
}

法二

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}public void run(){//读取小明输入的记录个数&＃xff0c;并创建相应大小的数组Scanner scanner &＃61; new Scanner(System.in);final int N &＃61; scanner.nextInt();//创建记录数据的ListLinkedList data &＃61; new LinkedList();//读取N次访问记录for(int i &＃61; 0; i < N; i&＃43;&＃43;){data.add(scanner.nextInt());}String result &＃61; "";//引入一个Map来存储数字出现的次数&＃xff0c;Key为读者编号&＃xff0c;Value为访问的次数Map map &＃61; new HashMap();for(int i &＃61; 0; i < data.size(); i&＃43;&＃43;){int id &＃61; data.get(i); //得到一个读者的编号Integer count &＃61; map.get(id); //从map中读取次数if(count &＃61;&＃61; null){ //若读取到的为null&＃xff0c;则说明之前没有访问过result &＃43;&＃61; 1 &＃43; " ";map.put(id, 1); //往map中添加put的次数}else{ //若之前有访问过count&＃43;&＃43;; //访问次数&＃43;1map.put(id, count); //将&＃43;1后的数据覆盖原来的访问次数result &＃43;&＃61; count &＃43; " ";}}System.out.println(result); //输出结果}
}

&＃xff08;以上两份代码&＃xff0c;为了更容易看懂&＃xff0c;一些还可以更精简的地方没有精简&＃xff1b;如数据的读取。&＃xff09;

From&＃xff1a;陈祖煌

Blog&＃xff1a;http://my.oschina.net/chenzuhuang/blog

转载必须说明出处

----------------------------------------------------------------------------------------------------------