图书馆读者访问记录

Sat May 09 22:57:43 CST 2015 682 算法

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

问题

【问题描述】

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

【输入格式】

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

第二行输入N个访问记录的读者编号(正整数),用空格隔开。

【输出格式】

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

【输入样例】

5

1 2 1 3 1

【输出样例】

1 1 2 1 3 


分析

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

法一

可以考虑用一个嵌套循环解决:

设数组为data[N]

  1. 从data中位置 i (0<=i<N)处拿到一个编号data[i],定义计数器count = 0;

  2. 从数组的位置0处开始到 i,对每一个 j (0<=j<=i)若有data[j] == data[i],则count++.

  循环代码:

?

1
2
3
4
5
6
7
8
9
for(int i = 0; i < N; i++){
    int count = 0;   //记数器
    for(int j = 0; j <= i; j++){
        if(data[i] == data[j]){
        count++;
    }
    }
    result += count + " ";
}


问题解决。


法二

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

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

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

思路大致如此:

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

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

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
String result = "";
//引入一个Map来存储数字出现的次数,Key为读者编号,Value为访问的次数
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
         
for(int i = 0; i < data.size(); i++){
    int id = data.get(i);        //得到一个读者的编号
    Integer count = map.get(id);    //从map中读取次数
    if(count == null){            //若读取到的为null,则说明之前没有访问过
    result += 1 " ";
    map.put(id, 1);            //往map中添加put的次数
    }
    else{               //若之前有访问过
    count++;            //访问次数+1
    map.put(id, count);        //将+1后的数据覆盖原来的访问次数
    result += count + " ";
    }
}



代码

以下为完整代码:

法一

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        new Main().run();
    }
     
    public void run(){
        //读取小明输入的记录个数,并创建相应大小的数组
        Scanner scanner = new Scanner(System.in);
        final int N = scanner.nextInt();
         
        //创建记录数组
        int[] data = new int[N];
        //读取N次访问记录
        for(int i = 0; i < N; i++){
            data[i] = scanner.nextInt();
        }
         
        //处理
        String result = "";
        for(int i = 0; i < N; i++){
            int count = 0;   //记数器
            for(int j = 0; j <= i; j++){
                if(data[i] == data[j]){
                    count++;
                }
            }
            result += count + " ";
        }  
        System.out.println(result); //输出结果
    }
}



法二

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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(){
        //读取小明输入的记录个数,并创建相应大小的数组
        Scanner scanner = new Scanner(System.in);
        final int N = scanner.nextInt();
         
        //创建记录数据的List
        LinkedList<Integer> data = new LinkedList<Integer>();
         
        //读取N次访问记录
        for(int i = 0; i < N; i++){
            data.add(scanner.nextInt());
        }
         
        String result = "";
        //引入一个Map来存储数字出现的次数,Key为读者编号,Value为访问的次数
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
         
        for(int i = 0; i < data.size(); i++){
            int id = data.get(i);            //得到一个读者的编号
            Integer count = map.get(id); //从map中读取次数
            if(count == null){                //若读取到的为null,则说明之前没有访问过
                result += 1 " ";
                map.put(id, 1);                //往map中添加put的次数
            }
            else{                           //若之前有访问过
                count++;                    //访问次数+1
                map.put(id, count);            //将+1后的数据覆盖原来的访问次数
                result += count + " ";
            }
        }
         
        System.out.println(result); //输出结果
    }
}


(以上两份代码,为了更容易看懂,一些还可以更精简的地方没有精简;如数据的读取。)


打赏
打赏

分享到: