三元组的最小距离问题|数据结构常见小题05

欢迎大家在评论区分享自己遇到的算法题目，小编看到的话就会进行回复！

三元组(a,b,c), a b c分别取自S1 S2 S3(三个升序序列)
三元组的距离公式D=|a-b|+|b-c|+|c-a|
求所有三元组中，距离最小的三元组，及其距离

本质上是最大元素与最小元素距离的二倍，计算距离极值即可

最笨的方法，但是简单容易接收。
使用三层循环求出所有距离，找出最小距离

int findMinDistance1(int S1[], int l1, int S2[], int l2, int S3[], int l3){
    int minCombin[3] = {S1[0], S2[0], S3[0]}, minDistance, D;
    minDistance = Distance(S1[0], S2[0], S3[0]);
    for(int i=0;iD){
                    minDistance = D;
                    minCombin[0] = S1[i];
                    minCombin[1] = S2[j];
                    minCombin[2] = S3[k];
                }
            }
        }
    }
    cout <<'('< 
算法2 
最小项移位对比的方法，时间复杂度O(n)
 两个要点：
 
找到三个元素中最小的那个
每次循环只改变（增大）最小元素的值
 
int findMinDistance2(int S1[], int l1, int S2[], int l2, int S3[], int l3){
    int a, b, c;
    a = S1[0];
    b = S2[0];
    c = S3[0];
    int i = 0, j = 0, k = 0;
    int minD = Distance(S1[0], S2[0], S3[0]),D;
    while(i 
测试 
int main(){
    int S1[3] = {-1,0,9}, 
        S2[4]={-25,-10,10,11}, 
        S3[5]={2,9,17,30,41};
    int minD1 = findMinDistance1(S1,3,S2,4,S3,5);
    int minD2 = findMinDistance2(S1,3,S2,4,S3,5);
    cout< 
结果：
 (9,10,9)
 2
 2
 
 
小结 
第二种算法带一些数学思维，在以后的应用中常常会出现在小细节处。