- getMutualFriends()
use one set to store friends from the other guy and collect all the friends of you that is in the set.
给你一个getfriends的function然后写找共同好友 (s1.retainAll(s2)). T:O(n)
2.suggest（）
排序好友的好友，谁共同好友多就放前面。。
每个都问了下run time
第2题我有点卡了，最后提示用了hashmap但我不知道map怎么用value来排序。。
/**
* Created by Zirui Tao on 9/8/2018.
*/
import java.util.*;
public class Friends {
String name;
List<Friends> friends;
public static void main(String [] args){
Friends me = new Friends("zirui");
Friends zero = new Friends("zero");
Friends one = new Friends("one");
Friends two = new Friends("two");
Friends three = new Friends("three");
Friends four = new Friends("four");
me.friends = Arrays.asList(one, two ,three);
zero.friends = Arrays.asList(one, three, four);
one.friends = Arrays.asList(me, zero, two ,three, four);
two.friends = Arrays.asList(me, one);
three.friends = Arrays.asList(me, zero, one, four);
four.friends = Arrays.asList(zero, one, three);
// me.findCommon(zero);
me.rank(zero);
}
public Friends(String name, List<Friends> friends){
this.name= name;
this.friends = friends;
}
public Friends(String name){
this.name= name;
this.friends = null;
}
public List<Friends> findCommon(Friends o){
// O(n)
Set<Friends> set = new HashSet<Friends>(o.friends);
set.retainAll(this.friends);
// set.forEach(n -> System.out.print(n.name + " "));
// System.out.println();
return new ArrayList<>(set);
}
public void rank(Friends o){
// <Integer, String>; find the O(n): n: size of friends
Map<Integer, List<String>> rank = new HashMap<>();
for (Friends f: this.findCommon(o)){
int key = this.findCommon(f).size();
List<String> l = rank.getOrDefault(key, new ArrayList<String>());
l.add(f.name);
rank.put(key,l);
}
// traverse through the friends ranks map O(n ^2) since print takes O(n)
for ( int i = this.friends.size(); i >= 0; i--){
if (rank.get(i) != null) {
rank.get(i).forEach(x -> System.out.print(x));
System.out.println();
}
}
System.out.println();
// alternatively using sort: O(n^2logn) since sort takes O(nlogn) to sort and O(n) to print
// SortedSet<Integer> keys = new TreeSet<>(new Comparator<Integer>(){
// @Override
// public int compare(Integer i1, Integer i2){
// return i2 - i1;
// }
// });
//
// keys.addAll(rank.keySet());
//// keys.forEach(x-> rank.get(x).forEach(y->System.out.print(y)));
// for(Integer key: keys){
// rank.get(key).forEach(x-> System.out.print(x));
// System.out.println();
// }
}
}