寻找三元组的最小距离

2020

  1. 定义三元组(a,b,c)的距离为D=|a-b|+|b-c|+|c-a|，给定3个非空整数集合S1、S2、S3按照升序分别存储在3个数组中。
  2. 请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)中的最小距离。

image-20230703093452787

1.枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
给定3个非空整数集合S1、S2和S3、按照升序分别存储在3个数组中
设计一个算法计算出 所有可能的三元组 中的最小距离
*/
#include "preset.h"

#define Max 0x7fffffff

//计算绝对值
int cul(int a, int b, int c) {
    return abs(a - b) + abs(b - c) + abs(c - a);
}

//判定是否为最小值
bool isMin(int a, int b, int c) {
    if (min(a, min(b, c)) == a) {
        return true;
    }
    return false;
}

int minTri(SqList a, SqList b, SqList c) {
    int i = 0, j = 0, k = 0;
    int ans = Max;
    while (i < a.length && j < b.length && k < c.length && ans >= 0) {
        int temp = cul(a.elem[i], b.elem[j], c.elem[k]);
        if (temp < ans) ans = temp;
        if (isMin(a.elem[i], b.elem[j], c.elem[k])) i++;
        else if (isMin(b.elem[i], a.elem[j], c.elem[k])) j++;
        else k++;
    }
    cout << "min_i = " << i << " min_j = " << j << " min_k = " << k << endl;
    return ans;
}

int main() {
    SqList a = {{-1, 0, 9}, 3};
    SqList b = {{-25, -10, 10, 11}, 4};
    SqList c = {{2, 9, 17, 30, 41}, 5};
    cout << minTri(a, b, c) << endl;
    return 0;
}

2.暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//暴力法
#include "preset.h"

//计算绝对值
int cul(int a, int b, int c) {
    return abs(a - b) + abs(b - c) + abs(c - a);
}

//暴力循环法
int minTri(SqList a, SqList b, SqList c) {
    int min_i, min_j, min_k;
    int min = cul(a.elem[0], b.elem[0], c.elem[0]);
    for (int i = 0; i < a.length; ++i) {
        for (int j = 0; j < b.length; ++j) {
            for (int k = 0; k < c.length; ++k) {
                int temp = cul(a.elem[i], b.elem[j], c.elem[k]);
                if (temp < min) {
                    min = temp;
                    min_i = i;
                    min_j = j;
                    min_k = k;
                }
            }
        }
    }
    cout << "min_i = " << min_i << " min_j = " << min_j << " min_k = " << min_k << endl;
    return min;
}

int main() {
    SqList a = {{-1, 0, 9}, 3};
    SqList b = {{-25, -10, 10, 11}, 4};
    SqList c = {{2, 9, 17, 30, 41}, 5};
    cout << minTri(a, b, c) << endl;
    return 0;
}