文章
211
粉丝
0
获赞
0
访问
46.5k
(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(...
登录后发布评论
暂无评论,来抢沙发