数据结构
2020-41
定义三元组(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）说明你所设计算法的时间复杂度和空间复杂度。
答案
1）算法的基本设计思想
利用距离公式 D = |a-b| + |b-c| + |c-a| = 2 × (max(a,b,c) - min(a,b,c))，问题转化为求三个有序数组中三个数的最大值与最小值之差的最小值。采用三指针方法，分别指向三个数组的起始位置，每次计算当前三元组的距离并更新最小值，然后移动指向当前三个数中最小值的指针，以尝试减小差值。直到任一指针到达数组末尾，算法结束。
2）算法描述（C语言）
int abs(int a) { // 绝对值计算
if (a < 0) return -a;
else return a;
}
bool minjg(int a, int b, int c) { // 判断a是不是最小值
if (a <= b && a <= c) return true;
else return false;
}
int findMin(int A[], int n, int B[], int m, int C[], int p) {
int i = 0, j = 0, k = 0, D, Dmin = MAX_SIZE;
while (i < n && j < m && k < p && Dmin > 0) {
// 循环条件是下标i、j、k还在集合内，并且Dmin不为0
D = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(A[i] - C[k]);
if (D < Dmin) Dmin = D;
if (minjg(A[i], B[j], C[k])) i++;
else if (minjg(B[j], C[k], A[i])) j++;
else k++;
}
return Dmin;
}3）时间复杂度和空间复杂度
- 时间复杂度：O(n1 + n2 + n3)，其中 n1, n2, n3 分别为三个数组的长度。每个指针最多遍历其数组一次，总操作次数与数组长度和成线性关系。
- 空间复杂度：O(1)，只使用了常量额外空间。