题目描述
“臭味相投”——这是我们描述朋友时喜欢用的词汇。
两个人是朋友通常意味着他们存在着许多共同的兴趣。
然而作为一个宅男,你发现自己与他人相互了解的机会并不太多。
幸运的是,你意外得到了一份北大图书馆的图书借阅记录,于是你挑灯熬夜地编程,想从中发现潜在的朋友。
首先你对借阅记录进行了一番整理,把 N 个读者依次编号为 1,2,…,N,把 M 本书依次编号为 1,2,…,M。
同时,按照“臭味相投”的原则,和你喜欢读同一本书的人,就是你的潜在朋友。
你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。
样例
4 5
2
3
2
1
算法
(巧妙利用数据结构) $O(n^2)$
1.该题类似于投票箱的题目。我们可以把每本书当作一个盒子,如果喜欢就往里面对应编号的盒子投票。盒子可以用数组来完成,数组下标为书籍编号,内容为该书籍获得的票数。
2.每个人可以用Map数据结构来保存,其中key为每个人的编号,value为每个盒子的编号也就是数组的下标。
3.在取出“臭味相投”朋友数时,判断每个人value对应下标的数组值如果为1那么说明没有朋友直接返回BeiJu,否则返回数组值-1(因为该值包含了自己的一票)。
Java 代码
public class Main {
public void getMyfriend(int[] param,int count) {
HashMap<Integer,Integer> map = new HashMap<>();
int[] a = new int[count+1];
for (int i = 0; i < param.length;i++) {
a[param[i]]++;
map.put(i,param[i]);
}
for (int value : map.values()) {
if (a[value] == 1) {
System.out.println("BeiJu");
}else {
System.out.println(a[value] - 1);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = scanner.nextInt();
}
Main num01 = new Main();
num01.getMyfriend(a,M);
}
}