13.png

    1. /*
    2. 已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,是的组成的三元组距离最小。三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为:
    3.   Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)
    4.   请设计一个求最小三元组距离的最优算法,并分析时间复杂度。
    5. */
    6. #include <stdio.h>
    7. #include <math.h>
    8. int dis(int a,int b,int c) {//返回距离
    9. return abs(a - b) + abs(b - c) + abs(a - c);
    10. }
    11. int min(int a,int b,int c) {//返回当前最小值,此时便移动它的指针
    12. if (a < b&&a < c) return a;
    13. else if(b < c&&b < a) return b;
    14. else return c;
    15. }
    16. int findMinofTrip(int *s1,int *s2,int *s3,int len1,int len2,int len3) {
    17. int i=0, j=0, k = 0;//数组下标,遍历数组
    18. int Max = 1000;//设定一个最大值,假定为1000
    19. int nowD = 0;
    20. while (i<len1&&j<len2&&k<len3) {
    21. nowD = dis(s1[i],s2[j],s3[k]);
    22. if (nowD < Max) Max = nowD;//进行更新
    23. if (s1[i] == min(s1[i], s2[j], s3[k])) i++;
    24. else if (s2[j] == min(s1[i], s2[j], s3[k])) j++;
    25. else k++;
    26. }
    27. return Max;
    28. }
    29. int main() {
    30. int S1[] = { -1,0,9 };
    31. int S2[] = { -25,-10,10,11 };
    32. int S3[] = {2,9,17,30,41};
    33. int minD = findMinofTrip(S1,S2,S3,3,4,5);
    34. return 0;
    35. }