Massive Algorithms: Snapchat- Group Record using Union-find

Snapchat- Group Record using Union-find

// 题目是手机上的通讯录，每条记录只有(name, number)这种pair,有些记录名字重复，有些记录号码重复，让我返回一个list>， // 将所有记录按人分组。比较tricky的点在于(ABC,123), (ABC, 456), (BCD, 456) // 三条记录，第一条和第三条也属于同一个人。要求时间复杂度尽量小

uf算法我是明白的，但是我想的时候的困惑在于

1.ufMap里面存放什么，是map还是map还是别的什么

2.在group的时候，既要对name进行uf group又要对number进行group怎么操作

解决方案是这样的（既union-find部分的思路）

1.首先ufMap里面存<Record, Record>，初始化把所有entry过一遍，都存入，使它最初的root节点都是它自己

2. find部分。

　　1）首先找到这个record的root节点

　　2）然后把从这个record开始直到root节点所有的节点的root节点都更新成root

　　3）返回root

3. union部分，没什么特别的

　　1）对record1,record2找到root1,root2

　　2）如果root1 != root2，那么就设置其中一个是另外一个的root节点

完成union-find的部分，整个算法的整体思路是。

1.建立一个nameMap<nameString, Record>和一个numMap<number, Record>

2.对于所有entry走一遍，

　　1) 如果nameMap里面已经存在当前entry的name，那么就说明要union；否则就把[nameString, entry]加入map

　　2）如果numMap里面已经存在当前entry的number，那么就说明要union；否则就把[number, entry]加入map
3. 所以此刻ufMap里面已经有已经对于name和number group之后的结果，现在就需要把结果保存下来。

　　所以可以先建一个Map<String, List<Record>>整理好，再根据这个map得到List<List<Record>>

实际代码如下：

public class GroupRecord {
    static class Record {
        String name;
        int number;
        public Record(String name, int number) {
            this.name = name;
            this.number = number;
        }

        public String toString() {
            return "(" + name + "," + number + ")";
        }
    }

    public static List<List<Record>> group(List<Record> records) {
        Map<Record, Record> ufMap = new HashMap<Record, Record>();
        Map<String, Record> nameMap = new HashMap<>();
        Map<Integer, Record> numMap = new HashMap<>();
        for(Record entry: records) {
            ufMap.put(entry, entry);
        }
        for(Record entry: records) {
            if(nameMap.containsKey(entry.name)) {
                union(ufMap, entry, nameMap.get(entry.name));
            } else {
                nameMap.put(entry.name, entry);
            }
            if(numMap.containsKey(entry.number)) {
                union(ufMap, entry, numMap.get(entry.number));
            } else {
                numMap.put(entry.number, entry);
            }
        }
        Map<String, List<Record>> groupMap = new HashMap<>();
        for(Record entry: records) {
            Record root = find(ufMap, entry);
            List<Record> list = groupMap.get(root.name);
            if(list == null) {
                list = new ArrayList<Record>();
            }
            list.add(entry);
            groupMap.put(root.name, list);
        }
        List<List<Record>> res = new ArrayList<List<Record>>(groupMap.values());
        return res;
    }

    private static Record find(Map<Record, Record> ufMap, Record record) {
        Record root = record;
        while(!ufMap.get(root).equals(root)) {
            root = ufMap.get(root);
        }
        Record cur = record;
        while(!cur.equals(root)) {
            ufMap.put(record, root);
            cur = ufMap.get(cur);
        }
        return root;
    }

    private static void union(Map<Record, Record> ufMap, Record r1, Record r2) {
        Record root1 = find(ufMap, r1);
        Record root2 = find(ufMap, r2);
        if(!root1.equals(root2)) {
            ufMap.put(root1, root2);
        }
    }

    public static void main(String[] args) {
        List<List<Record>> res = new ArrayList<List<Record>>();
        ArrayList<Record> records = new ArrayList<>();
        records.add(new Record("ABC",123));
        records.add(new Record("ABC",456));
        records.add(new Record("BCD",456));

        records.add(new Record("AD",342));
        records.add(new Record("AddD",11));
        records.add(new Record("DFX",34));
        records.add(new Record("AD",34));
        records.add(new Record("AD",11));

        res = group(records);
        System.out.println(res);
    }
}

Snapchat- Group Record using Union-find

Labels

Popular Posts