golang 解法, 执行用时: 152 ms, 内存消耗: 9 MB, 提交时间: 2022-11-30 12:50:11

func trulyMostPopular(names []string, synonyms []string) []string {
    count := make(map[string]int)  //存放名字对应的频率
    father := make(map[string]string) //存放名字对应的祖宗名字

    for _, v := range names {
        idx1 := strings.Index(v, "(")
        idx2 := strings.Index(v, ")")
        cnt := v[idx1+1: idx2]
        name := v[:idx1]
        num, _ := strconv.Atoi(cnt) 
        count[name] = num
        //初始时每个名字的祖先为自己
        father[name] = name 
    }

    for _, syn := range synonyms {
        idx := strings.Index(syn, ",")
        name1 := syn[1:idx]
        name2 := syn[idx+1:len(syn)-1]
        //选出字典序最小的名字作为name1
        father1 := find(name1, father)
        father2 := find(name2, father)
        
        if father1 == "" {
            father[father1] = father2
            continue
        }

        if father2 == "" {
            father[father2] = father1
            continue
        }

        if father1 > father2 {
            father1, father2 = father2, father1
        }
        //将father2 并入 father1
        if father1 != father2 {
            count[father1] += count[father2]
            father[father2] = father1
            delete(count, father2)
        }
    }

    ans := []string{}
    for name, cnt := range count {
        s := fmt.Sprintf("%s(%d)", name, cnt)
        ans = append(ans, s)
    } 
    return ans
}

//找到名字对应的祖先名字， 并使用路径压缩进行优化
func find(s string, f map[string]string) string {
    if f[s] != s {
        f[s] = find(f[s], f)
    }
    return f[s]
}

python3 解法, 执行用时: 212 ms, 内存消耗: 19.3 MB, 提交时间: 2022-11-30 12:48:46

class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        p, d, q = {}, {}, collections.defaultdict(int)
        for s in synonyms:
            a, b = s[1: -1].split(',')
            pa, pb = p.setdefault(a, [a]), p.setdefault(b, [b])
            if pa is not pb:    #并查集基操，对数组引用进行合并
                pa.extend(pb)
                for c in pb:
                    p[c] = pa
        for name in p:
            d.setdefault(id(p[name]), min(p[name])) #取字典序最小名
        for s in names:
            i = s.find('(')
            name, count = s[: i], int(s[i + 1: -1])
            q[name in p and d[id(p[name])] or name] += count    #未合并过的name单独计数
        return [f'{name}({count})' for name, count in q.items()]

java 解法, 执行用时: 55 ms, 内存消耗: 49.6 MB, 提交时间: 2022-11-30 11:34:09

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, String> unionMap = new HashMap<>();     //并查集， key(子孙)->value(祖宗)
        for (String name : names) {     //统计频率
            int idx1 = name.indexOf('(');
            int idx2 = name.indexOf(')');
            int frequency = Integer.valueOf(name.substring(idx1 + 1, idx2));
            map.put(name.substring(0, idx1), frequency);
        }
        for (String pair : synonyms) {  //union同义词
            int idx = pair.indexOf(',');
            String name1 = pair.substring(1, idx);
            String name2 = pair.substring(idx + 1, pair.length() - 1);
            while (unionMap.containsKey(name1)) {   //找name1祖宗
                name1 = unionMap.get(name1);
            }
            while (unionMap.containsKey(name2)) {   //找name2祖宗
                name2 = unionMap.get(name2);
            }
            if(!name1.equals(name2)){   //祖宗不同，要合并
                int frequency = map.getOrDefault(name1, 0) + map.getOrDefault(name2, 0);    //出现次数是两者之和
                String trulyName = name1.compareTo(name2) < 0 ? name1 : name2;
                String nickName = name1.compareTo(name2) < 0 ? name2 : name1;
                unionMap.put(nickName, trulyName);      //小名作为大名的分支，即大名是小名的祖宗
                map.remove(nickName);       //更新一下数据
                map.put(trulyName, frequency);
            }
        }
        String[] res = new String[map.size()];
        int index = 0;
        for (String name : map.keySet()) {
            StringBuilder sb = new StringBuilder(name);
            sb.append('(');
            sb.append(map.get(name));
            sb.append(')');
            res[index++] = sb.toString();
        }
        return res;
    }
}

javascript 解法, 执行用时: 292 ms, 内存消耗: 66.2 MB, 提交时间: 2022-11-30 11:29:49

/**
 * @param {string[]} names
 * @param {string[]} synonyms
 * @return {string[]}
 */
var trulyMostPopular = function (names, synonyms) {
    let map = {}
    const get = (names) => {
        if (!map[names]) map[names] = names
        return map[names] == names ? names : get(map[names])
    }
    const merge = (a, b) => {
        let ra = get(a), rb = get(b)
        if (rb < ra) {
            map[ra] = map[rb]
        } else {
            map[rb] = map[ra]

        }
    }
    synonyms.forEach((v) => {
        let [a, b] = v.slice(1, -1).split(',')
        merge(a, b)
    })
    let ret = new Map

    names.forEach(v => {
        let [a, names, cnt] = /^(.+)\((\d+)\)$/.exec(v)
        let k = get(names), vr = cnt - 0
        ret.set(k, (ret.get(k) || 0) + vr)
    })
    return [...ret].map(([name, v]) => {
        return `${name}(${v})`
    })
};