请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

猿媛之家

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 6797|回复: 0

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

[复制链接]

412

主题

474

帖子

1526

积分

金牌会员

Rank: 6Rank: 6

积分
1526
发表于 2015-12-12 10:42:04 | 显示全部楼层 |阅读模式

       N个未排序的整数,在线性时间内,求这N个整数在数轴上相邻两个数之间的最大差值(请写出关键算法)

       解题方法:仅供参考

       由于指明了要求为线性时间内,也就是 T(n)=O(n) ,所以不可以采用排序算法,因为最优排序算法复杂度为 O(nlogn) , 所以必须以空间换时间,采用位图技术,对所给元素进行赋值,得到其在数轴上的位置,也就是排序。

       然后再求得位图中 两个 1 之间的最大距离,此处约定相邻两点间距离为1;
       具体代码如下(仅供参考)

  1. int maxDistance(const vector &v)
  2. {
  3. if (v.empty())
  4. return 0;

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

  7. //初始化位图,值全部为0
  8. for (int i = 0; i < 100; i++)
  9. bitMap[i] = 0;

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

  12. //设置该元素所在位图坐标值为1
  13. for (int i = 0; i < len; i++)
  14. {
  15. bitMap[v[i]] = 1;
  16. }

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

  27. //pos位置处有第一个初始元素
  28. c = 1;
  29. for (int i = pos+1; i < 100 && c  maxdis)
  30. {
  31. maxdis = tmp;
  32. }//if
  33. tmp = 0;
  34. c++;
  35. }//else
  36. }//for

  37. return maxdis;

  38. }

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

  42. int maxdis = maxDistance(v);

  43. cout << maxdis << endl;

  44. system(“pause”);
  45. return 0;

  46. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|猿媛之家    

GMT+8, 2022-1-29 08:42 , Processed in 0.186593 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表