婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择字典序最小的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
提示：

names.length <= 100000
通过次数4,955提交次数12,076

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/baby-names-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        int n = names.length;
        int[] parent = new int[n];
        int[] freq = new int[n];
        Map<String,Integer> map = new HashMap<>();
        Map<Integer,String> map2 = new HashMap<>();

        //初始化
        int sign =0;
        for(String tname:names){
            int index = tname.indexOf("(");
            String name = tname.substring(0,index);                         // 获取名字
            String count = tname.substring(index+1,tname.length()-1);       // 获取数量

            map.put(name,sign);
            map2.put(sign,name);

            parent[sign] = sign;
            freq[sign] = Integer.valueOf(count);

            sign++;
        }

        //合并
        for(String synonym:synonyms){
            String temp = synonym.substring(1,synonym.length()-1);
            String[] arr = temp.split(",");

            Integer preIndex = map.get(arr[0]);                             // 获取名字对应的sign
            Integer aftIndex = map.get(arr[1]);                             // 获取名字对应的sign

            if(preIndex == null || aftIndex == null){
                continue;
            }

            while(preIndex != parent[preIndex]){                            // find              
                preIndex = parent[preIndex];
            }

            while(aftIndex != parent[aftIndex]){                            // find
                aftIndex = parent[aftIndex];
            }

            if(aftIndex.equals(preIndex)){                                  // 两个节点的祖先相同
                continue;
            }

            if(map2.get(preIndex).compareTo(map2.get(aftIndex)) >0){        // 字典序
                parent[preIndex] = aftIndex;                                // 合并，将parent[preIndex]合并到afterIndex
                freq[aftIndex] += freq[preIndex];                           // 计数整合
            }else{
                parent[aftIndex] = preIndex;                                // 合并，将parent[afterIndex]合并到preIndex
                freq[preIndex] += freq[aftIndex];
            }
        }

        //找根节点
        StringBuffer ans = new StringBuffer();
        for(int i=0;i<n;i++){
            if(parent[i] == i){
               String re = map2.get(i) + "("+freq[i]+")";
               ans.append(re);
               ans.append(",");
            }
        }

        return ans.toString().split(",");
    }
}

作者：jiu-wei-eh
链接：https://leetcode-cn.com/problems/baby-names-lcci/solution/6ci-acwei-guo-zui-hou-fa-xian-shi-fu-qin-42aq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信