文章

100

粉丝

0

获赞

0

访问

10.6k

头像
2020年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年8月28日 17:30
阅读数 36

(1)思路:
使用三个指针(i, j, k)分别遍历三个数组。每次计算当前三元组(S1[i], S2[j], S3[k])的距离,并更新最小距离。然后,移动指向最小值的那个指针(因为这样有可能缩小范围)。重复直到某个数组遍历完毕。

(2)

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

int findMinDistance(int S1[], int n1, int S2[], int n2, int S3[], int n3) {
    int i = 0, j = 0, k = 0;
    int min_dist = INT_MAX;
    
    while (i < n1 && j < n2 && k < n3) {
        int a = S1[i], b = S2[j], c = S3[k];
        int dist = computeDistance(a, b, c);
        if (dist < min_dist) {
            min_dist = dist;
        }
        
        // 找出当前三元组中的最小值
        if (a <= b && a <= c) {
            i++;   // 移动S1的指针
        } else if (b <= a && b <= c) {
            j++;   // 移动S2的指针
        } else {
            k++;   // 移动S3的指针
        }
    }
    
    return min_dist;
}

(3)每个指针最多移动各自数组的长度(n1, n2, n3)。因此,总循环次数最多为 n1+n2+n3n1+n2+n3。
所以时间复杂度为 O(n1+n2+n3)O(...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发