首页 > 代码库 > Snapchat- Group Record using Union-find
Snapchat- Group Record using Union-find
最近一直在做面筋，就没有在这边更新！但是最近！没有偷懒！
// 题目是手机上的通讯录，每条记录只有(name, number)这种pair,有些记录名字重复，有些记录号码重复，让我返回一个list<list<Record>>，
// 将所有记录按人分组。比较tricky的点在于(ABC,123), (ABC, 456), (BCD, 456)
// 三条记录，第一条和第三条也属于同一个人。要求时间复杂度尽量小
uf算法我是明白的，但是我想的时候的困惑在于
1.ufMap里面存放什么，是map<Record, Record>还是map<String, String>还是别的什么
2.在group的时候，既要对name进行uf group又要对number进行group怎么操作
解决方案是这样的（既union-find部分的思路）
1 1.首先ufMap里面存<Record, Record>，初始化把所有entry过一遍，都存入，使它最初的root节点都是它自己 2 3 2. find部分。 4 5 1）首先找到这个record的root节点 6 7 2）然后把从这个record开始直到root节点所有的节点的root节点都更新成root 8 9 3）返回root10 11 3. union部分，没什么特别的12 13 1）对record1,record2找到root1,root214 15 2）如果root1 != root2，那么就设置其中一个是另外一个的root节点
完成union-find的部分，整个算法的整体思路是。
1 1.建立一个nameMap<nameString, Record>和一个numMap<number, Record> 2 3 2.对于所有entry走一遍， 4 5 1) 如果nameMap里面已经存在当前entry的name，那么就说明要union；否则就把[nameString, entry]加入map 6 7 2）如果numMap里面已经存在当前entry的number，那么就说明要union；否则就把[number, entry]加入map 8 3. 所以此刻ufMap里面已经有已经对于name和number group之后的结果，现在就需要把结果保存下来。 9 10 所以可以先建一个Map<String, List<Record>>整理好，再根据这个map得到List<List<Record>>
实际代码如下：
1 public class GroupRecord { 2 static class Record { 3 String name; 4 int number; 5 public Record(String name, int number) { 6 this.name = name; 7 this.number = number; 8 } 9 10 public String toString() {11 return "(" + name + "," + number + ")";12 }13 }14 15 public static List<List<Record>> group(List<Record> records) {16 Map<Record, Record> ufMap = new HashMap<Record, Record>();17 Map<String, Record> nameMap = new HashMap<>();18 Map<Integer, Record> numMap = new HashMap<>();19 for(Record entry: records) {20 ufMap.put(entry, entry);21 }22 for(Record entry: records) {23 if(nameMap.containsKey(entry.name)) {24 union(ufMap, entry, nameMap.get(entry.name));25 } else {26 nameMap.put(entry.name, entry);27 }28 if(numMap.containsKey(entry.number)) {29 union(ufMap, entry, numMap.get(entry.number));30 } else {31 numMap.put(entry.number, entry);32 }33 }34 Map<String, List<Record>> groupMap = new HashMap<>();35 for(Record entry: records) {36 Record root = find(ufMap, entry);37 List<Record> list = groupMap.get(root.name);38 if(list == null) {39 list = new ArrayList<Record>();40 }41 list.add(entry);42 groupMap.put(root.name, list);43 }44 List<List<Record>> res = new ArrayList<List<Record>>(groupMap.values());45 return res;46 }47 48 private static Record find(Map<Record, Record> ufMap, Record record) {49 Record root = record;50 while(!ufMap.get(root).equals(root)) {51 root = ufMap.get(root);52 }53 Record cur = record;54 while(!cur.equals(root)) {55 ufMap.put(record, root);56 cur = ufMap.get(cur);57 }58 return root;59 }60 61 private static void union(Map<Record, Record> ufMap, Record r1, Record r2) {62 Record root1 = find(ufMap, r1);63 Record root2 = find(ufMap, r2);64 if(!root1.equals(root2)) {65 ufMap.put(root1, root2);66 }67 }68 69 public static void main(String[] args) {70 List<List<Record>> res = new ArrayList<List<Record>>();71 ArrayList<Record> records = new ArrayList<>();72 records.add(new Record("ABC",123));73 records.add(new Record("ABC",456));74 records.add(new Record("BCD",456));75 76 records.add(new Record("AD",342));77 records.add(new Record("AddD",11));78 records.add(new Record("DFX",34));79 records.add(new Record("AD",34));80 records.add(new Record("AD",11));81 82 res = group(records);83 System.out.println(res);84 }85 }
Snapchat- Group Record using Union-find
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。