[经典面试题][阿里]三元组最小距离

  1. 云栖社区>
  2. 博客列表>
  3. 正文

[经典面试题][阿里]三元组最小距离

sjf0115 2015-02-21 11:06:00 浏览782 评论0

摘要: 题目 已知三个升序整数数组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 ]|) 请设计一个求最小三元组距离的最优算法,并分析时间复杂度。

题目

已知三个升序整数数组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) (每次循环总有一个下标走了一步)。

代码

    /*---------------------------------------------
    *   日期:2015-02-21
    *   作者:SJF0115
    *   题目: 三元组最小距离
    *   来源:阿里
    *   博客:
    -----------------------------------------------*/
    #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;
            }//if
            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
                if(a[i] < b[j]){
                    if(a[i] < c[k]){
                        ++i;
                    }//if
                    else{
                        ++k;
                    }//else
                }//if
                else{
                    if(b[j] < c[k]){
                        ++j;
                    }//if
                    else{
                        ++k;
                    }//else
                }//else
            }//for
            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;
    }

如果有好的思路,可以留言。。。。。

【云栖快讯】阿里云栖开发者沙龙(Java技术专场)火热来袭!快来报名参与吧!  详情请点击

网友评论

sjf0115
文章828篇 | 关注54
关注
一款阿里巴巴自主研发的高性能、分布式的关系型数据库,支持完整的ACID特性。它高度兼容MyS... 查看详情
提供了高性能可伸缩的容器应用管理服务,支持在一组云服务器上通过Docker容器来进行应用生命... 查看详情
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
双12

双12