721. Accounts Merge

Version # 2 DFS[TODO]
非常需要做一下，现在写不动了


二刷 08/2022

Version #1 Union Find

Time - Here N is the number of accounts and K is the maximum length of an account.

Time complexity: O(NKlogNK)

Space O(NK)

Runtime: 67 ms, faster than 40.75% of Java online submissions for Accounts Merge.

Memory Usage: 67.4 MB, less than 24.80% of Java online submissions for Accounts Merge.

class Solution {

    class UF {

        Set<String>[] emails;

        int[] id;

        String[] names;

        public UF(List<List<String>> accounts) {

            int n = accounts.size();

            emails = new Set[n];

            id = new int[n];

            names = new String[n];

            for (int i = 0; i < n; i++) {

                emails[i] = new HashSet<>();

                for (int j = 1; j < accounts.get(i).size(); j++) {

                    emails[i].add(accounts.get(i).get(j));

                }

                id[i] = i;

                names[i] = accounts.get(i).get(0);

            }

        }

        

        public int root(int i) {

            while (id[i] != i) {

                id[i] = id[id[i]];

                i = id[i];

            }

            return i;

        }

        

        public void union(int p, int q) {

            if (p == q) {

                return;

            }

            int rootP = root(p);

            int rootQ = root(q);

            if (rootP == rootQ) {

                return;

            }

            if (emails[rootP].size() < emails[rootQ].size()) {

                id[rootP] = rootQ;

                for (String email : emails[rootP]) {

                    emails[rootQ].add(email);

                }

            } else {

                id[rootQ] = rootP;

                for (String email : emails[rootQ]) {

                    emails[rootP].add(email);

                }

            }

        }

    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        UF uf = new UF(accounts);

        // key-email, value-one of the account index

        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < accounts.size(); i++) {

            List<String> account = accounts.get(i);

            for (int j = 1; j < account.size(); j++) {

                String email = account.get(j);

                if (map.containsKey(email)) {

                    uf.union(i, map.get(email));

                }

                map.put(email, i);

            }

        }

        List<List<String>> result = new ArrayList<>();

        for (int i = 0; i < accounts.size(); i++) {

            if (uf.id[i] != i) {

                continue;

            }

            List<String> account = new ArrayList<>(uf.emails[i]);

            Collections.sort(account);

            account.add(0, uf.names[i]);

            result.add(account);

        }

        return result;

    }

}

一刷
Version #1 Union Find
精髓在于如何建图
一开始觉得既然每个email都有一个owner不如用owner作为parent，但实际上是不可行的，union find中所有的node都需要是同类型的data
因为就算当前这个owner name是parent，之后union完了还是会成为一个child
这里省略的weighted graph的步骤，因为感觉代码有些复杂
所以对于n个nodes 的amertized time complexity 是NlogN
本题的N是整个accounts list里面email的总数，也就是UF里面的node的总数
Time O(NlogN)
Space O(N)

77.17 %
class Solution {
    // key->node, value->id
    private Map<String, String> parent;
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> result = new ArrayList<>();
        if (accounts == null || accounts.size() == 0) {
            return result;
        }
        // key->email, value->owner
        Map<String, String> owner = new HashMap<>();
        parent = new HashMap<>();
       
        for (List<String> account : accounts) {
            if (account.size() < 2) {
                continue;
            } 
            String firstEmail = account.get(1);
            owner.put(firstEmail, account.get(0));
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if(parent.containsKey(email)) {
                    union(firstEmail, root(email));
                } else {
                    parent.put(email, firstEmail);
                }
            }
        }
       
       
        // TODO
        Map<String, TreeSet<String>> parentToEmails = new HashMap<>();
        for (Map.Entry<String, String> entry : parent.entrySet()) {
            String root = root(entry.getKey());
            if (!parentToEmails.containsKey(root)) {
                parentToEmails.put(root, new TreeSet<>());
            }
            parentToEmails.get(root).add(entry.getKey());
        }
       
        for (Map.Entry<String, TreeSet<String>> entry : parentToEmails.entrySet()) {
            List<String> temp = new ArrayList<>(entry.getValue());
            temp.add(0, owner.get(entry.getKey()));
            result.add(temp);
        }
        return result;
    }
   
    private String root(String i) {
        while (parent.get(i) != i) {
            parent.put(i, parent.get(parent.get(i)));
            i = parent.get(i);
        }
        return i;
    }
   
    private void union(String p, String q) {
        String rootP = root(p);
        String rootQ = root(q);
        if (rootP.equals(rootQ)) {
            return;
        }
        parent.put(rootP, rootQ);
    }
}