题目
已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,是的组成的三元组距离最小。三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为:
Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)
请设计一个求最小三元组距离的最优算法,并分析时间复杂度。
思路
保持三个下标索引 i,j,k,找出a[i],b[j],c[k]里最小的元素。如果a[i]最小, 则下一次循环 i=i+1, 其他两个索引不变。如果b[j]最小, 则下一次循环 j=j+1, 其他两个索引不变。如果c[k]最小, 则下一次循环 k=k+1, 其他两个索引不变。如此循环,直至最小的数对应的下标到达该数组尾部。记录最小距离。
时间复杂度:O(l+m+m) (每次循环总有一个下标走了一步)。
代码
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
class Solution {
public:
int MinDistance(int a[],int l,int b[],int m,int c[],int n){
if(l <= 0 || n <= 0 || m <= 0){
return -1;
}
int min = INT_MAX;
int dis = 0,first = 0,second = 0,third = 0;
for(int i = 0,j = 0,k = 0;i < l && j < m && k < n;){
dis = max(max(abs(a[i]-b[j]),abs(a[i]-c[k])),abs(b[j]-c[k]));
if(dis < min){
min = dis;
first = i;
second = j;
third = k;
}
if(a[i] < b[j]){
if(a[i] < c[k]){
++i;
}
else{
++k;
}
}
else{
if(b[j] < c[k]){
++j;
}
else{
++k;
}
}
}
cout<<"First->"<<first<<" Second->"<<second<<" Third->"<<third<<endl;
return min;
}
};
int main() {
Solution solution;
int a[] = {5,16,20};
int b[] = {13,14,15,17,35};
int c[] = {19,22,24,29,32,42};
int l = 3,m = 5,n = 6;
int result = solution.MinDistance(a,l,b,m,c,n);
cout<<result<<endl;
}
如果有好的思路,可以留言。。。。。
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
STM32+ESP8266(AT固件)连接阿里云物联网系列保姆级教学 阿里云物联网 三元组解析工具 阿里云工具 物联网工具 三元组解析 ESP8266工具
连接阿里云MQTT物联网平台三元组密码生成工具
三元组转置以顺序表排列。 #include #include <stdlib.h> #define MAX 1000 //矩阵中非0元素的个数 typedef int ElemType; //定义三元组 typedef struct { int row,col; //非零元素的行号列号 ElemType e; ...
基于 Pytorch 的深度学习三元组抽取
数据结构 矩阵与三元组表 c++ 数据结构 矩阵与三元组表 c++
用三元组的形式表示二叉树的结构,建立二叉树,并利用栈的方式和递归方式实现中序遍历。
基于windows窗体程序的三元组表的稀疏矩阵
用c++程序给出了三元组的实现方法及例程。
动态分配内存 三元组代码Triplet_动态存储分配_引用版
使用py2neo存储将三元组存储到neo4j图形数据库中,构建知识图谱。知䇶图䉡(KQRZOHdJH GUaSK)以结构化的形式描䘠客㿲世界中概念、实体及 其关系,将互㚄㖁的信息㺘䗮成更接䘁人类䇔知世界的形式,提供了一种更好地 ...
用C++写的三元组表 采用的是严蔚敏的C语言教材改变的 呵呵,分享下哈
//稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 //非零元个数最大为100 typedef struct {int i,j; //非零元的行下标和列下标 ElemType e; //非零元 }Triple; typedef struct {Triple data[MAXSIZE+1]; //...
里面有数据结构三元组表的应用,很直观 typedef double Datatype; typedef struct { int i,j; Datatype v; }SNode;//三元组元素类型描述 typedef struct { int mu,nu,tu; SNode data[Max]; }SPMatrix;//三元组...
利用三元组表对稀疏矩阵实现加法、减法及转置运算
用三元组表示稀疏矩阵,实现稀疏矩阵的乘法。对于乘法结果得到的结果矩阵,设计一个算法,寻找该矩阵的鞍点【最大选题人数:5】 提示:二维数组的鞍点:如果存在一个这样的元素,它是所在行上最大的元素,同时又...
三元组压缩存储 数组实现和链表实现……
本程序以三元组表存储稀疏矩阵,可进行矩阵相加及转置运算。 TSMatrix A,B,C,D; cout请输入矩阵A和B的行数 列数 "; cin>>A.m>>A.n; B.m=C.m=D.m=A.m; B.n=C.n=D.n=A.n; cout请输入A中的非零元素个数: "; ...
三元组是学数据结构的第一个实验,一定好好做
三元组表的建立及矩阵输出 三元组表的建立及矩阵输出
稀疏矩阵的三元组程序,完全正确.稀疏矩阵的三元组存储