Skip to content

2020年 408 数据结构 第 41 题

数据结构2020年综合题8分

题目 ​

定义三元组 (a, b, c)(a, b, c 均为正数)的距离 D = |a - b| + |b - c| + |c - a|。给定 3 个非空整数集合 S₁, S₂, S₃,按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法,计算并输出所有可能的三元组 (a, b, c)(a ∈ S₁, b ∈ S₂, c ∈ S₃)中的最小距离。

例如,S₁ = {-1, 0, 9},S₂ = {-25, -10, 10, 11},S₃ = {2, 9, 17, 30, 41},则最小距离为 2,相应的三元组为 (9, 10, 9)。

要求:

(1) 给出算法的基本设计思想。

(2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数