2023年华为OD机考真题：关联端口组合并

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：关联端口组合并
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
有M（1<=M<=10）个端口组，每个端口组是长度为N(1<=N<=100)的整数数组，如果端口组间存在2个及以上不同端口相同，则认为这两个端口组互相关联，可以合并。
第一行输入端口组个数M，再输入M行，每行逗号分隔，代表端口组，输出合并后的端口组用二维数组表示
输入描述：
端口组内数字可以重复
输出描述：
1.组内相同端口仅保留一个，从小到大排序。
2.组外顺序保持输入顺序
补充说明：
M，N不再限定范围内，统一输出一组空数组[[]]
示例1
输入：
4
4
2,3,2
1,2
5
输出：
[[4],[2,3],[1,2],[5]]
说明：
仅有一个端口2相同，不可以合并
示例2
输入：
3
2,3,1
4,3,2
5
输出：
[[1,2,3,4],[5]]
说明：
存在两个2,3有交集，可以合并
示例3
输入：
6
10
4,2,1
9
3,6,9,2
6,3,4
8
输出：
[[10],[1,2,3,4,6,9],[9],[8]]
示例4
输入：
11
输出：
[[]]
说明：
11超出范围，输出[[]]
解题思路：
将输入的组合转化为set集合（有去重和排序的功能），加入list集合中
每输入一个组合，则对list进行遍历，找出其中有两个并集的集合进行合并，合并完加入原来list集合中。再次执行步骤2
注意：两个需要合并的集合都需要从list中删除，且并集需要加在靠前的位置（题目要求组外保持输入顺序）

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 关联端口组合并
 * @Description 有M（1<=M<=10）个端口组，每个端口组是长度为N(1<=N<=100)的整数数组，如果端口组间存在2个及以上不同端口相同，则认为这两个端口组互相关联，可以合并。
 * 第一行输入端口组个数M，再输入M行，每行逗号分隔，代表端口组，输出合并后的端口组用二维数组表示
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();

        if (M > 10) {
            System.out.println("[[]]");
        } else {
            List<Set<String>> list = new ArrayList<>();
            sc.nextLine();

            for (int i = 0; i < M; i++) {
                String[] strings = sc.nextLine().split(",");
                Set<String> set = new TreeSet<>();
                if (strings.length == 1) {    //只有一个元素直接添加
                    set.add(strings[0]);
                    list.add(set);
                } else {
                    //数组转化为set集合
                    set.addAll(Arrays.asList(strings));
                    list.add(set);
                    merge(set, list, list.size() - 1);
                }
            }

            System.out.println(list);
        }
    }

    /**
     * 合并关联端口组合
     *
     * @param set   进行合并的端口组合
     * @param list  端口组合集合
     * @param index 需要进行合并的组合索引
     */
    public static void merge(Set<String> set, List<Set<String>> list, int index) {

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

            if (i == index) {
                continue;
            }

            Set<String> setIndex = list.get(i);     //当前索引的set集合

            Set<String> setTemp = new TreeSet<>();
            setTemp.addAll(set);
            setTemp.retainAll(setIndex);    //求出set和setIndex的交集

            if (setTemp.size() >= 2) {  //交集大于等于2则合并

                set.addAll(setIndex);   //set与setIndex合并

                int beforeIndex = Math.min(index, i);    //求出排在前面的index
                int afterIndex = beforeIndex == index ? i : index;  //靠后的位置

                list.remove(afterIndex);     //合并的两个set进行删除，先删除后面的一个
                list.remove(beforeIndex);
                list.add(beforeIndex, set);    //将新的set放在前面位置

                merge(set, list, beforeIndex);     //将新建的组合再进行判断合并

            }
        }
    }
}