正文

BAT面试题 - 找一个无序实数数组中的最大差值

IP云
IP云V管理员/2 阅读
09/25
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描写叙述：

一个无序的实数数组a[i]。要求求里面大小相邻的实数的差的最大值。比方 double a[]={1,5,4,0.2,100} 这个无序的数组，相邻的数的最大差值为100-5=95.

题目分析：这题有个简单的做法。首先就是对数组进行一个排序。然后扫面一遍数据就能够得到结果。但时间复杂度依赖于排序时间复杂度，一般为O（nlog n）。
然而一般面试官会让给出一个线性空间和线性时间复杂度的算法。这时就用到了桶排序的思想。

解题思路

解题步骤例如以下：
  1. 扫面一遍数组。找到数组中的最大max，最小min值。
  2. 将[min, max]区间平均分为n-1个区间段（每一个区间段相应一个桶bucket），每一个桶用一对有序实数对[a,b] 来表示桶内的数。
  3. 再次从头到尾扫描数组，将每一个元素加入到对应的桶bucket里面。

    注意：有的桶为空（不含不论什么数据）

  4. 然后按顺序訪问每一个（非空）的相邻的桶进行比較。

    若两个非空的相邻的桶分别为(a,b) , (c,d)，那么这两个非空相邻的桶的距离为 c-b。最后选择最大的非空相邻同的距离返回就可以。

注意：
  • 上述算法是空间和时间复杂度均是O(n)
  • 我们不须要计算桶内元素的距离（如b-a）。由于数组最大间隔max-min分成n-1个桶。n个元素中一定有两个相邻元素的距离大于桶内的距离（想一想抽屉原理或者鸽巢原理），所以桶内的距离是不用算的

源码：C++

在算法的实现上，注意桶为空的标记。
此外为了方便。算法实现过程中，桶内保存的不是对应的元素，而是对应元素在数组中对应的index。

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
/*
*一个无序的实数数组，求它们近期邻的两个值的差
**/
double maxDiff(double a[], int n){
double max = a[0];
double min = a[0];
for (int i=1; i<n; ++i){
if (max < a[i]){
max = a[i];
}
if (min > a[i]){
min = a[i];
}
}
double bar = (max - min)/(n-1);
int pos;
//pair<first,second> : first表示桶的左边界index。second表示桶的右边界index
vector< pair<int,int> > buckets(n,make_pair(-1,-1));
//这里桶内存对应数据的下标，而不是对应的数据，方便后面的数据计算，以免有精度损失。
for (int i=0; i<n; i++){
pos = (int)((a[i] - min)/bar);
if ((buckets[pos].first == -1) && (buckets[pos].second == -1)){ //下标比較，若为double型比較注意精度问题
buckets[pos].first = buckets[pos].second = i;
}else{
if (a[buckets[pos].first] > a[i])
buckets[pos].first = i;
if (a[buckets[pos].second] < a[i])
buckets[pos].second = i;
}
}
int lastIx=0;
double max_diff = 0;
double tmp_diff = 0;
for (int i=1; i<n; ++i){ //计算桶之间的距离
if ((buckets[i].first == -1) && (buckets[i].second == -1)){
//桶为空的标志,不处理
}else{
tmp_diff = a[buckets[i].first] - a[buckets[lastIx].second];
if (tmp_diff > max_diff){
max_diff = tmp_diff;
}
lastIx = i;//lastIx指上一个非空桶的index。且第一个桶和最后一个桶肯定非空。
}
}
return max_diff;
}
int main(){
double a[]={2,4,8,16,19.0,7,7,30};
cout<<maxDiff(a,8)<<endl;
return 0;
}

备注：
这道题网上有人给出了对应的解法，但对桶为空的标记没有处理好，不能好好的work。如：http://blog.csdn.net/joanlynnlove/article/details/7706194

转载请注明出处：http://blog.csdn.net/acema/article/details/38682943