AC111-计算三个有序数组中所有可能三元组的最小距离

三元组 (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)。（2020 年统考题）

代码实现

// 函数 abs：计算整数的绝对值
int abs(int a) {
    if (a < 0) {
        return -a; // 如果 a 是负数，则返回其相反数
    } else {
        return a;  // 如果 a 是非负数，则直接返回 a
    }
}

// 函数 f1：计算三个有序数组中所有可能三元组的最小距离
int f1(int S1[], int m, int S2[], int n, int S3[], int p) {
    int i = 0, j = 0, k = 0;           // 初始化三个指针，分别指向三个数组的起始位置
    int min_dis = 100000;              // 初始化最小距离为一个较大的值（1e5）

    // 循环条件：三个指针均未超出各自数组的范围
    while (i < m && j < n && k < p) {
        // 计算当前三元组 (S1[i], S2[j], S3[k]) 的距离
        int dis = abs(S1[i] - S2[j]) + abs(S1[i] - S3[k]) + abs(S2[j] - S3[k]);

        // 如果当前距离小于已知的最小距离，则更新最小距离
        if (dis < min_dis) {
            min_dis = dis;
        }

        // 策略性地移动指针：移动指向最小元素的指针
        if (S1[i] <= S2[j] && S1[i] <= S3[k]) {
            i++; // 如果 S1[i] 是三个元素中最小的，则移动指针 i
        } else if (S2[j] <= S1[i] && S2[j] <= S3[k]) {
            j++; // 如果 S2[j] 是三个元素中最小的，则移动指针 j
        } else {
            k++; // 否则移动指针 k（即 S3[k] 是最小的）
        }
    }

    return min_dis; // 返回计算得到的最小距离
}

---

代码逻辑解析

距离公式理解

三元组(a,b,c)的距离定义为：D = |a-b| + |b-c| + |c-a|

这个公式实际上表示三个点在数轴上两两之间的距离之和。

核心思想

1. 贪心策略：每次移动指向最小元素的指针
2. 理由：由于数组已排序，移动最小元素的指针有可能使三个元素更接近，从而减小距离

算法步骤

1. 初始化：三个指针分别指向各自数组的开始位置
2. 计算距离：对当前三个元素计算距离公式
3. 更新最小值：如果当前距离更小，则更新最小距离
4. 移动指针：移动指向最小元素的指针
5. 重复：直到某个指针超出数组范围

---

示例分析

给定： - S1 = {-1, 0, 9} - S2 = {-25, -10, 10, 11}
- S3 = {2, 9, 17, 30, 41}

执行过程示意：

步骤	i	j	k	S1[i]	S2[j]	S3[k]	距离计算	最小距离
1	0	0	0	-1	-25	2	24+3+27=54	54
2	0	1	0	-1	-10	2	9+3+12=24	24
3	0	2	0	-1	10	2	11+3+8=22	22
...	...	...	...	...	...	...	...	...
最终	2	2	1	9	10	9	1+0+1=2	2

---

时间复杂度分析

• 循环次数：
• 每次循环至少会移动一个指针
• 最坏情况下，每个指针最多移动其对应数组的长度次
• 总的循环次数为 O(m + n + p)

• 如果三个数组长度相近（都为n），则时间复杂度为 O(n)

• 每次循环的操作：

• 距离计算和比较操作都是常数时间 O(1)
• 指针移动决策也是常数时间 O(1)

总体时间复杂度：O(m + n + p)

---

空间复杂度分析

• 算法只使用了常量级别的额外空间：
• 指针变量：i, j, k
• 距离变量：min_dis, dis
• 没有使用与输入规模相关的额外数组或数据结构

空间复杂度：O(1)

---

关键算法思想解释

为什么移动最小元素的指针？

这是算法的核心贪心思想：

1. 直观理解：要使三个数的距离最小，应该让它们尽可能接近
2. 数学依据：当三个数中有一个明显较小时，增大这个最小值可能使三者更接近
3. 效率考虑：由于数组已排序，移动最小元素的指针是最有可能改善距离的策略

图解说明

在数轴上表示三个元素的位置：

S2[j] ---- S1[i] -------- S3[k]
  ↓
较小   中等        较大

移动 S2[j] 的指针（最小值）到下一个元素，可能使三者更接近：

    S1[i] ---- S2[j+1] --- S3[k]
      ↓
    中等    变大        较大

---

延伸知识点

1. 距离公式的几何意义

距离 D = |a-b| + |b-c| + |c-a| 实际上是三个点在数轴上构成的"周长"： - 当三个点重合时，距离为0（最小） - 当三个点分散时，距离增大

2. 算法优化思路

• 预处理：如果数组很大，可以先进行去重等预处理
• 并行化：对于超大数据集，可以考虑分段并行计算
• 近似算法：对于实时性要求高的场景，可以使用近似算法

3. 相关问题变种

• k元组最小距离：扩展到k个数组的情况
• 最大距离：寻找最大距离的三元组
• 距离范围查询：找出距离在某个范围内的所有三元组

4. 实际应用场景

• 数据分析：寻找多维数据中的相似点
• 机器学习：特征选择中的距离计算
• 信号处理：多通道信号的同步检测