代码:
写了一个超时版本 又学了并查集
超时版本:
class Solution {public List<List<String>> accountsMerge(List<List<String>> accounts) {List<List<String>> newAcc = new ArrayList<>();Set<Integer> isArrive = new HashSet<>();int idx = 0;Iterator<List<String>> iterator = accounts.iterator();while(iterator.hasNext()){List<String> curAcc = iterator.next();if(isArrive.contains(idx)){idx++;continue;}Set<Integer> set = new HashSet<>();set.add(idx);set = getIdx(idx,set,accounts);List<String> curEmail = new ArrayList<>();for(int i:set){for(String str:accounts.get(i)){if(!curEmail.contains(str))curEmail.add(str);}}if(!isArrive.contains(idx)){String name = curEmail.get(0);curEmail.remove(0);Collections.sort(curEmail); curEmail.add(0,name);newAcc.add(curEmail);isArrive.add(idx);for(int i:set){isArrive.add(i);}}idx++;} return newAcc;}public Set<Integer> getIdx(int curIdx, Set<Integer> set, List<List<String>> accounts){List<String> curAccount = accounts.get(curIdx);// curAccount.remove(0);for(String email:curAccount){for(int i=0;i<accounts.size();i++){if(set.contains(i))continue;List<String> acc = accounts.get(i);if(acc.contains(email)&&email.contains("@")){set.add(i);set = getIdx(i,set,accounts);}}}return set;}
}
并查集版:
class Solution {public List<List<String>> accountsMerge(List<List<String>> accounts) {Map<String,Integer> emailToIndex = new HashMap<String,Integer>();Map<String,String> emailToName = new HashMap<String,String>();int emailsCount = 0;for(List<String>account:accounts){//遍历 写email的序号 和 email的name对String name = account.get(0);int size = account.size();for(int i=1;i<size;i++){String email = account.get(i);if(!emailToIndex.containsKey(email)){emailToIndex.put(email,emailsCount++);emailToName.put(email,name);}}}UnionFind uf = new UnionFind(emailsCount);for(List<String> account:accounts){ //把同一个人的邮箱合并到一个父节点下String firstEmail = account.get(1);int firstIndex = emailToIndex.get(firstEmail);int size = account.size();for(int i=2;i<size;i++){String nextEmail = account.get(i);int nextIndex = emailToIndex.get(nextEmail);uf.union(firstIndex,nextIndex);}}Map<Integer,List<String>> indexToEmails = new HashMap<Integer,List<String>>();for(String email:emailToIndex.keySet()){//把相同根节点的email放一起int index = uf.find(emailToIndex.get(email));List<String> account = indexToEmails.getOrDefault(index, new ArrayList<String>());account.add(email);indexToEmails.put(index, account);}List<List<String>> merged = new ArrayList<List<String>>();for(List<String> emails:indexToEmails.values()){Collections.sort(emails);String name = emailToName.get(emails.get(0));List<String> account = new ArrayList<>();account.add(name);account.addAll(emails);merged.add(account);}return merged;}
}
class UnionFind{int[] parent;public UnionFind(int n){parent = new int[n];for(int i=0;i<n;i++){parent[i]=i;}}public void union(int index1,int index2){parent[find(index2)] = find(index1);}public int find(int index){if(parent[index]!=index){parent[index] = find(parent[index]);}return parent[index];}
}