[C算法]005-寻找最小的三元组距离

均采用C语言来编写，版本为C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

题目

2020年真题

定义三元组 $(a,b,c) (a,b,c \text{ 均为整数})$ 的距离 $D=|a-b|+|a-c|+|b-c|$。
给定三个非空整数集合 $S_1$，$S_2$ 和 $S_3$，按升序分别存储在3个数组中。

请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)(a∈S1,b∈S2,c∈S3)$ 中最小距离。
例如：$S_1=\{-1,0,9\}，S_2=\{-25,-10,10,11\}，S_3=\{2,9,17,30,41\}$，则最小距离为2，相应的三元组为 $(9,10,9)$。

分析

这道算法既考察数学洞察力，也考察对双指针（在这里是三指针）技巧的运用。让我们一步步来拆解它。

首先，我们看这个距离公式：$D=|a-b|+|a-c|+|b-c|$。乍一看它包含三个绝对值，计算起来似乎有点繁琐。

为了简化问题，假设 $a \le b \le c$
在这种假设下，我们计算得 $|a-b|+|a-c|+|b-c|=2c-2a$
也就是 $D=2\times(\text{最大}-\text{最小})$

然后，题目中确实给了升序的条件，所以我们直接找寻最大值和最小值的差值的最小值即可，应该还是赢容易的，我们只要不断更新最小值（向后移动），不断更新更小的结果，就行。

代码实现

#include <limits.h>
#include <stdio.h>

int min_val(int a, int b, int c) {
    if (a <= b && a <= c)return a;
    if (b <= a && b <= c)return b;
    return c;
}

int max_val(int a, int b, int c) {
    if (a >= b && a >= c)return a;
    if (b >= a && b >= c)return b;
    return c;
}

void find_min_of_trip(int a[], int a_size, int b[], int b_size, int c[], int c_size) {
    int i = 0, j = 0, k = 0;
    int min_D = INT_MAX;
    int result_a = 0, result_b = 0, result_c = 0;
    // 这里既保证了数组不会越界，也保证了不需要多余的查找（查到一个数组末尾就说明已经是最好的结果了，因为数组是升序的）
    while (i < a_size && j < b_size && k < c_size) {
        int min_temp = min_val(a[i], b[j], c[k]);
        int max_temp = max_val(a[i], b[j], c[k]);
        int cur_D = 2 * (max_temp - min_temp); // 使用 2max-2min 计算距离
        if (cur_D < min_D) {
            min_D = cur_D;
            result_a = a[i];
            result_b = b[j];
            result_c = c[k];
            if (min_D == 0)break;
        }

        if (min_temp == a[i]) i++;
        else if (min_temp == b[j]) j++;
        else k++;
    }

    printf("最小距离为%d，三元组是(%d,%d,%d)", min_D, result_a, result_b, result_c);
}

int main() {
    int s1[] = {-1, 0, 9};
    int s2[] = {-25, -10, 10, 11};
    int s3[] = {2, 9, 17, 30, 41};
    find_min_of_trip(s1, 3, s2, 4, s3, 5);
    return 0;
}

复杂度分析

时间复杂度：O(a_n + b_n + c_n)
空间复杂度：O(1)