1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

题意要求将多个实体匹配系统输出的实体结果进行去重、合并与排序。 每个系统的输出可视为一个集合,若两个集合存在交集,则它们应被合并为一个更大的集合。

这实际上是一个并查集(Union-Find) 的典型应用场景:

  • 每个实体可以看作一个节点;
  • 若两个实体在同一系统结果中出现,则它们属于同一连通分量;

P4343.第2题-实体匹配结果合并问题

    1000ms Tried: 1705 Accepted: 398 Difficulty: 5 所属公司 : 华为
    算法与标签>并查集

题目内容

某业务部门有多个数据来源,现在需要对多个来源的实体数据进行去重、消歧、合并。有多个实体匹配系统(假设系统的匹配结果完全正确),每个系统从不同角度进行匹配,匹配结果是相同实体列表。

这些匹配结果中往往存在交叉重复的问题,需要对所有匹配结果进行合并去重。例如系统 AAA 的匹配结果是 ["111", "222"] ,系统 BBB 的匹配结果是 ["222", "333"],那么合并后的匹配结果是 ["111", "222", "333"]。请你按照上述逻辑,编写代码实现对匹配结果的合并去重。

输入描述

  • 第一行输入是整数 NNN,表示有 NNN 个实体匹配系统,1<=N<=100001<=N<=100001<=N<=10000 ;

  • 接下来 NNN 行是每个实体匹配系统的匹配结果(相同实体列表,每行实体数量不超过 100100100 );实体使用数字字符串表示(字符长度不超过 101010),实体之间通过空格分开。实体种类数量不超过 100000100000100000 。

输出描述

输出 MMM 行(M<=NM <= NM<=N),每行内容是合并后的匹配结果。

注意,每行的输出结果需要按照字典顺序进行排序;合并后的匹配结果列表之间,也需要按字典顺序进行排序。

样例1

输入

5
1 2 3
4 5
11 22
33 44 55 1
3 66

输出

1 2 3 33 44 55 66
11 22
4 5

说明

匹配结果 "111 222 333 "、"333333 444444 555555 111"、"333 666666",存在重复实体 "111" 和 "333",故可以合并,合并后按字典序为 "111 222 333 333333 444444 555555 666666";

另外两组结果与其他组不存在重复;

合并后的匹配结果列表之间,按字典序排序后输出,即样例输出所示内容。

样例2

输入

2
1 2
2 3

输出

1 2 3

说明

有两组匹配结果,即 "111 222"和"222 333",存在重复实体 "222",故可以合并为 "111 222 333"。

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 1223ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?