programmer001 发表于 2015-12-12 10:42:04

2015大众点评研发工程师笔试题 (算法题)

       N个未排序的整数,在线性时间内,求这N个整数在数轴上相邻两个数之间的最大差值(请写出关键算法)       解题方法:仅供参考       由于指明了要求为线性时间内,也就是 T(n)=O(n) ,所以不可以采用排序算法,因为最优排序算法复杂度为 O(nlogn) , 所以必须以空间换时间,采用位图技术,对所给元素进行赋值,得到其在数轴上的位置,也就是排序。       然后再求得位图中 两个 1 之间的最大距离,此处约定相邻两点间距离为1;
       具体代码如下(仅供参考)int maxDistance(const vector &v)
{
if (v.empty())
return 0;

//申请一个位图,(约定整数为100以内),否则位图大小应申请 INT_MAX
int *bitMap = new int;

//初始化位图,值全部为0
for (int i = 0; i < 100; i++)
bitMap = 0;

//所给元素的个数
int len = v.size();

//设置该元素所在位图坐标值为1
for (int i = 0; i < len; i++)
{
bitMap] = 1;
}

//maxdix值初始化为0,pos 记录第一个所给元素所在位置 , 声明一个临时变量c用于记录走过的所给元素个数,控制循环终止
int maxdis = 0 , pos =0 , c = 0 , tmp = 0 ;
for (int i = 0; i < 100; i++)
{
if (bitMap == 1)
{
pos = i;
break;
}//if
}//for

//pos位置处有第一个初始元素
c = 1;
for (int i = pos+1; i < 100 && cmaxdis)
{
maxdis = tmp;
}//if
tmp = 0;
c++;
}//else
}//for

return maxdis;

}

int main()
{
vector v = { 2, 3, 56, 23, 67, 8, 1, 45, 89 , 99 };

int maxdis = maxDistance(v);

cout << maxdis << endl;

system(“pause”);
return 0;

}

页: [1]
查看完整版本: 2015大众点评研发工程师笔试题 (算法题)