2020 年 408 数据结构 · 第 41 题

定义三元组 $(a,b,c)$ （ $a,b,c$ 均为正数）的距离 $D=|a-b|+|b-c|+|c-a|$ 。给定 $3$ 个非空整数集合 $S_1,S_2,S_3$ ，按升序分别存储在 $3$ 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)$ （ $a\in S_1,b\in S_2,c\in S_3$ ）中的最小距离。例如 $S_1=\{-1,0,9\},S_2=\{-25,-10,10,11\},S_3=\{2,9,17,30,41\}$ 。则最小距离为 $2$ ，相应的三元组为 $(9,10,9)$ 。

要求：

（1）给出算法的基本设计思想；

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释；

（3）说明你所设计算法的时间复杂度和空间复杂度