2013年阿里算法笔试题解题报告

2013年阿里算法笔试题解题报告

解答题：

1、有一个算法，查找n个元素的的数组的最大值和最小值，要比较2n次；请写一个最高效的算法，并说明他要比较的次数。请注意复杂度的常数

(不用写代码，说明步骤和过程即可，要定出比较的次数，没写不给分)

2、有三个非递减序列的数组a[l]、b[m]、c[n]，求他们之间的最小距离。已知距离的定义如下：

distance = max(|a[i]-b[j]|, |a[i]-c[k]|, |b[j]-c[k]|).其中0<=i<l, 0<=j<m, 0<=k<n

Answer:

1.一般情况下，我们是独立的找出最大和最小值这各需要n-1的比较，一共是2n-2次的比较，个人认为最高的效率是3(n/2),具体的方法记录已知的最小值和最大值，但是并不是将每一个输入元素与当前的最大最小值比较，（如果是的话，那么代价就是每个元素需要2次比较），而是对输入元素成对的进行比较。首先先对输入的一对元素进行比较，然后将较小的与当前最小值比较，较大的与当前最大值比较，这样对2个元素一个需要3次比较，相对于前面的4次比较

2.max(|a[i]-b[j]|, |a[i]-c[k]|, |b[j]-c[k]|),需求最小.这个问题很明显可以转化为区间上取点问题。

设数组a: a1, a2,a3......

b: b1,b2,b3......

c: c1,c2,c3......

在这三个数列中每列任选一点，使得三点中最大与最小值的差最小。可以使用贪心来做，先在第一列任意选取一点x，然后在第二列中贪心求得与x 的差最小的点y , 接着比较得出x,y 的最大值value, 最后重新贪心选取一遍，结果就可以得出来了，时间复杂度n^3.

Oh ，对了，题目中说了是非递减的，那么就是有序的，那么在用贪心在做选择的时候，如果比较的差值比之前的大，那么就可以跳出循环了，这样就可以剪枝掉一部分的数据。那么算法复杂度就会降下很多，具体的就要看数据。

如果各位有更好的想法，还希望能不吝赐教。