【408DS算法题】进阶011-20年真题_三元组的最小距离

Index

• • 真题题目
  • 分析实现
  • • 总结

真题题目

定义三元组(a, b, c)（a, b, c均为正数）的距离D = |a-b| + |b-c| + |c-a| 给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b, c) ( a ∈ S 1 , b ∈ S 2 , c ∈ S 3 ) (a\in S1, b\in S2, c\in S3) (a∈S1,b∈S2,c∈S3)中的最小距离。
例如S1={-1, 0, 9}，S2={-25, -10, 10, 11}，S3={2, 9, 17, 30, 41}，则最小距离为2，相应的三元组为(9, 10, 9)。要求：

1. 给出算法的基本设计思想。
2. 根据设计思想，采用C、C++或 Java 语言描述算法，关键之处给出注释。
3. 说明你所设计算法的时间复杂度和空间复杂度。

（本文重点关注算法实现思路，不含具体答题表述）

分析实现

我们先来分析实现题中出现的小模块——三元组的距离D。

具体实现如下：

#define INT MAXOx7fffffff
int abs(int a){//计算绝对值
	if(a<0) return -a;
	else return a;
}
bool xls_min (int a,int b,int c){//a是否是三个数中的最小值
	if (a<-b&&a<=c)return true;
	return false;
}
int findMinofTrip(int A[],int n,int B[],int m,int c[],int p){
	//D_min用于记录三元组的最小距离,初值赋为INT MAX
	int i=0, j=0, k=0,D_min=INT_MAX,D;
	while(i<n&&j<m&&k<p& &D_min>0){
		D=abs(A[i]-B[j]) +abs(B[j]-c[k])+abs(c[k]-A[i]); //计算Dif(D<D_min) 
		D_min=D;//更新D
		if(xls_min(A[i],B[j],c[k]))
			i++;	//更新a
		else if(xls_min(B[j],c[k],A[i]))
			j++;
		else 
			k++;
	}
	return D_min;
}

总结

以上就是通过定义三个指针，不断调整最小指针逐步进行扫描，以得出三数组构成三元组最小距离的过程。

本题的核心在于分析简化三元组的距离公式，根据简化后的公式可以相对顺利地得出优化后的解题方法。