有一些賬號，賬號里面有一個或多個email， 如果兩個賬號有共同的email，則認為這兩個賬號是同一個人，找出哪些賬號是同一個人 輸入是這樣的:數字是用戶，字母是郵箱，有很多人有多個郵箱，找出相同的用戶1- {x,y,z}2-{x} 3-{a,b}4-{y, z}5-{b}6-{m}7-{t,b}

賬號之間如果有公共email就連邊，我覺得要用hashMap, 存（email, user） pair

如果當前user的某個email在hashMap里出現過，當時是user1, 就看user和user1是否connected，否的話就要union,根據Union Find

Union Find Based on Quick Union

1 package fbOnsite; 2 import java.util.*; 3 class UnionFind{ 4 int[] ids; 5 int count; 6 public UnionFind(int num) { 7 ids = new int[num]; 8 Arrays.fill(ids, -1); 9 count = 0; 10 } 11 12 public int find(int id) { 13 while (id != ids[id]) id = ids[id]; 14 return id; 15 } 16 17 public void union(int n1, int n2) { 18 int root1 = find(n1); 19 int root2 = find(n2); 20 ids[root2] = root1; 21 } 22 23 public boolean isConnected(int n1, int n2) { 24 return find(n1) == find(n2); 25 } 26 } 27 28 public class EmailUser { 29 public int commonUser(HashMap<Integer, List<Character>> map) { 30 int size = map.size(); 31 UnionFind uf = new UnionFind(10); 32 HashMap<Character, Integer> emailToUser = new HashMap<Character, Integer>(); 33 for (int user : map.keySet()) { 34 uf.ids[user] = user; 35 uf.count++; 36 List<Character> emailList = map.get(user); 37 for (Character eachEmail : emailList) { 38 if (!emailToUser.containsKey(eachEmail)) { 39 emailToUser.put(eachEmail, user); 40 } 41 else { 42 int oriUser = emailToUser.get(eachEmail); 43 if (!uf.isConnected(user, oriUser)) { 44 uf.union(oriUser, user); 45 uf.count--; 46 } 47 } 48 } 49 } 50 for (int elem : uf.ids) 51 System.out.print(elem); 52 return uf.count; 53 } 54 55 /** 56 * @param args 57 */ 58 public static void main(String[] args) { 59 // TODO Auto-generated method stub 60 EmailUser sol = new EmailUser(); 61 HashMap<Integer, List<Character>> map = new HashMap<Integer, List<Character>>(); 62 map.put(0, new ArrayList<Character>()); 63 map.put(1, new ArrayList<Character>()); 64 map.put(2, new ArrayList<Character>()); 65 map.put(3, new ArrayList<Character>()); 66 map.put(4, new ArrayList<Character>()); 67 map.put(5, new ArrayList<Character>()); 68 map.put(6, new ArrayList<Character>()); 69 map.get(0).add('x'); 70 map.get(0).add('y'); 71 map.get(0).add('z'); 72 map.get(1).add('x'); 73 map.get(2).add('a'); 74 map.get(2).add('b'); 75 map.get(3).add('y'); 76 map.get(3).add('z'); 77 map.get(4).add('b'); 78 map.get(5).add('m'); 79 map.get(6).add('t'); 80 map.get(6).add('b'); 81 int res = sol.commonUser(map); 82 System.out.println(res); 83 } 84 85 }

?

轉載于:https://www.cnblogs.com/EdwardLiu/p/6569384.html

總結

以上是生活随笔為你收集整理的FB面经Prepare: Email User的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。