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