721. Accounts Merge - Medium

前往題目

之前寫的文章，果然這題全忘了😂

想法

• 名子無法當key，因為可能重複
• 唯一能辨別不同帳號的就只有兩個帳號都有出現相同的email，但這個email會在第一個嗎，還是有可能在任意位置…

思路

1. 利用union find疊代每一個帳號下的每一個email，如果發現當前帳號的某個email有和另一個帳號的一樣就union
2. 接著把相同account的email組合在一起
3. 最後把組合好的email排序一下，並且最前面加上帳戶名

Union find演算法解析

Code

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int size = accounts.size();

        UnionFind uf = new UnionFind(accounts.size());

        HashMap<String, Integer> emailToAcc = new HashMap<>();

        // Iterate the accounts
        for (int i = 0; i < size; ++i) {
            List<String> details = accounts.get(i);

            // Iterate the emails under the account
            for (int j = 1; j < details.size(); ++j) {
                String email = details.get(j);

                // Find the email
                if (emailToAcc.containsKey(email)) {
                    // Union the account because they're the same account
                    uf.union(i, emailToAcc.get(email));
                } else {
                    emailToAcc.put(email, i);
                }
            }
        }

        // Unique account -> emails of each account
        HashMap<Integer, List<String>> accToEmails = new HashMap<>();

        for (String key : emailToAcc.keySet()) {
            int root = uf.find(emailToAcc.get(key));
            
            if (!accToEmails.containsKey(root)) {
                accToEmails.put(root, new ArrayList<String>());
            }

            // Add the email to the account
            accToEmails.get(root).add(key);
        }

        // Collect the emails from accToEmails
        List<List<String>> mergedDetails = new ArrayList<>();

        for (Integer acc : accToEmails.keySet()) {
            // Store the emails
            List<String> emails = accToEmails.get(acc);

            // Sort the emails
            Collections.sort(emails);

            // Insert the account name
            emails.add(0, accounts.get(acc).get(0));

            mergedDetails.add(emails);
        }

        return mergedDetails;
    }

    class UnionFind {
        int[] parent;
        int[] weight;

        public UnionFind(int num) {
            parent = new int[num];
            weight = new int[num];

            for (int i = 0; i < num; i++) {
                parent[i] = i;
                weight[i] = 1;
            }
        }

        public boolean union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            // They are the same group already
            if (rootA == rootB) {
                return false;
            }

            // Union
            // Weight of rootA is heavier than rootB
            if (weight[rootA] > weight[rootB]) {
                // 小樹接到大樹
                parent[rootB] = rootA;
                // 更新權重，rootA變成更大顆的樹了
                weight[rootA] += weight[rootB];
            } else {
                parent[rootA] = rootB;
                weight[rootB] += weight[rootA];
            }
            return true;
        }

        // Find the root
        public int find(int a) {
            while (a != parent[a]) {
                // Path compression
                parent[a] = parent[parent[a]];
                a = parent[a];
            }
            return a;
        }
    }
}

2024/06/24

• 很難的一題，unionfind實作直接忘光
• 意外發現原先的code是TLE，原因是Path compression那邊，已修正