[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 <stdio.h>
#include <stdlib.h>
#include <limits.h> // 如果不想引用这个，D初始化为第一次计算的结果即可

int get_D(int a, int b, int c) {
    return abs(a - b) + abs(a - c) + abs(b - c);
}

void find_min_of_trip(int a[], int n_a, int b[], int n_b, int c[], int n_c) {
    int i = 0, j = 0, k = 0;
    
    // 初始化结果
    int min_D = get_D(a[0], b[0], c[0]);
    int result_a = a[0], result_b = b[0], result_c = c[0];

    while (i < n_a && j < n_b && k < n_c) {
        // 1. 计算当前距离
        int current_D = get_D(a[i], b[j], c[k]);
        
        // 2. 如果发现更优解，更新
        if (current_D < min_D) {
            min_D = current_D;
            result_a = a[i]; 
            result_b = b[j]; 
            result_c = c[k];
        }
        
        // 3. 贪心策略：谁最小，谁就往后移
        if (a[i] <= b[j] && a[i] <= c[k]) {
            i++;
        } else if (b[j] <= c[k]) { // 此时隐含了 b[j] < a[i]
            j++;
        } else {
            k++;
        }
    }

    printf("最小距离为%d，三元组为(%d, %d, %d)\n", 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;
}

寻找最小值的写法

// 我一开始的错误写法（迷宫一样的 if-else）
 while (a_i < a_len && b_i < b_len && c_i < c_len) {
     int new_D = get_D_of_trip(a[a_i], b[b_i], c[c_i]);
     if (new_D < D) {
         D = new_D;
         a_min = a[a_i];
         b_min = b[b_i];
         c_min = c[c_i];
     }
     if (a[a_i] < b[b_i]) {
         if (a[a_i] < c[c_i]) {
             a_i++;
         } else {
             c_i++; // c 最小
         }
     } else if (b[b_i] < c[c_i]) {
         b_i++; // b 最小
     } else {
         c_i++; // c 最小
     }
 }

while (i < n_a && j < n_b && k < n_c) {
    // 1. 计算当前距离
    int current_D = get_D(a[i], b[j], c[k]);
    
    // 2. 如果发现更优解，更新
    if (current_D < min_D) {
        min_D = current_D;
        result_a = a[i]; 
        result_b = b[j]; 
        result_c = c[k];
    }
    
    // 3. 贪心策略：谁最小，谁就往后移
    if (a[i] <= b[j] && a[i] <= c[k]) {
        i++;
    } else if (b[j] <= c[k]) { // 此时隐含了 b[j] < a[i]
        j++;
    } else {
        k++;
    }
}