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

要求：

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

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

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

顺序表

[tag_link]

分析，由D=∣a−b∣+∣b−c∣+∣c−a∣≥0得：① 当a=b=c时，距离最小。② 其余情况。不失一般性，假设观察下面的数轴： L1 =∣a−b∣，L2 =∣b−c∣，L3 =∣c−a∣，D=∣a−b∣+∣b−c∣+∣c−a∣=L1 +L2 +L3 =2L3由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a使得L3 =∣c−a∣最小。

1）算法的基本设计思想

• 使用Dmin记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
• 集合S1、S2和S3，分别保存在数组A、B、C中。数组的下标变量i=j=k=0，当i<S1、j<S2且k<S3时（∣S∣表示集合S中的元素个数），循环执行以下过程：
• 计算（A[i]，B[j]，C[j]）的距离D；（计算D）
• 若D<Dmin，则Dmin =D；（更新D)
• 将A[i]，B[i]，C[j]中的最小值的下标+1；（对照分析：最小值为a，最大值为c，这里c不变而更新a，试图寻找更小距离D）
• 输出Dmin，结束。

2）算法实现

void solve(int S1[], int n1, int S2[], int n2, int S3[], int n3) {
  int i = 0, j = 0, k = 0;
  int res = INT32_MAX;
  while (i < n1 && j < n2 && k < n3) {
    int a = S1[i], b = S2[j], c = S3[k];
    int D = abs(a-b) + abs(b-c) + abs(a-c);
    res = min(res, D);
    int v = min3(a, b, c);
    if (v == a) {
      i++;
    } else if (v == b) {
      j++;
    } else {
      k++;
    }
  }
  return res;
}

3）设n=∣S1 ∣+∣S2 ∣+∣S3 ∣，时间复杂度为O(n)，空间复杂度为O(1)。