LeetCode 721. 账户合并

Categories:

题目描述
思路分析
1. 解法一：并查集（推荐）
相似题目

题目描述

✅ 721. 账户合并

思路分析

解法一：并查集（推荐）

核心思路：

将每个邮箱映射为索引并加入并查集。

同一账户内的邮箱合并到同一集合。

最后按根节点收集邮箱并排序。

复杂度分析：

时间复杂度：O(N log N)，其中 N 为邮箱数量。

空间复杂度：O(N)，用于并查集与映射。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Integer> emailId = new HashMap<>();
        Map<String, String> emailName = new HashMap<>();

        int id = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (!emailId.containsKey(email)) {
                    emailId.put(email, id++);
                    emailName.put(email, name);
                }
            }
        }

        UnionFind uf = new UnionFind(id);
        for (List<String> account : accounts) {
            int firstId = emailId.get(account.get(1));
            for (int i = 2; i < account.size(); i++) {
                uf.union(firstId, emailId.get(account.get(i)));
            }
        }

        Map<Integer, List<String>> groups = new HashMap<>();
        for (String email : emailId.keySet()) {
            int root = uf.find(emailId.get(email));
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }

        List<List<String>> res = new ArrayList<>();
        for (List<String> emails : groups.values()) {
            Collections.sort(emails);
            String name = emailName.get(emails.get(0));
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(emails);
            res.add(account);
        }

        return res;
    }

    static class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx == ry) {
                return;
            }
            if (rank[rx] < rank[ry]) {
                parent[rx] = ry;
            } else if (rank[rx] > rank[ry]) {
                parent[ry] = rx;
            } else {
                parent[ry] = rx;
                rank[rx]++;
            }
        }
    }
}

import "sort"

func accountsMerge(accounts [][]string) [][]string {
	emailID := make(map[string]int)
	emailName := make(map[string]string)
	id := 0
	for _, account := range accounts {
		name := account[0]
		for i := 1; i < len(account); i++ {
			email := account[i]
			if _, ok := emailID[email]; !ok {
				emailID[email] = id
				emailName[email] = name
				id++
			}
		}
	}

	uf := newUnionFind(id)
	for _, account := range accounts {
		first := emailID[account[1]]
		for i := 2; i < len(account); i++ {
			uf.union(first, emailID[account[i]])
		}
	}

	groups := make(map[int][]string)
	for email, idx := range emailID {
		root := uf.find(idx)
		groups[root] = append(groups[root], email)
	}

	res := make([][]string, 0)
	for _, emails := range groups {
		sort.Strings(emails)
		name := emailName[emails[0]]
		account := make([]string, 0, len(emails)+1)
		account = append(account, name)
		account = append(account, emails...)
		res = append(res, account)
	}

	return res
}

type unionFind struct {
	parent []int
	rank   []int
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	return &unionFind{parent: parent, rank: rank}
}

func (uf *unionFind) find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) union(x int, y int) {
	rx := uf.find(x)
	ry := uf.find(y)
	if rx == ry {
		return
	}
	if uf.rank[rx] < uf.rank[ry] {
		uf.parent[rx] = ry
	} else if uf.rank[rx] > uf.rank[ry] {
		uf.parent[ry] = rx
	} else {
		uf.parent[ry] = rx
		uf.rank[rx]++
	}
}

相似题目

题目	难度	考察点
547. 省份数量	中等	并查集
684. 冗余连接	中等	并查集
990. 等式方程的可满足性	中等	并查集
399. 除法求值	中等	图
721. 账户合并	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/75888658