Chinaunix首页 | 论坛 | 博客
  • 博客访问: 362947
  • 博文数量: 181
  • 博客积分: 215
  • 博客等级: 民兵
  • 技术积分: 313
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-17 19:39
个人简介

王的男人

文章分类

全部博文(181)

文章存档

2016年(2)

2015年(35)

2014年(17)

2013年(84)

2012年(49)

我的朋友

分类:

2012-09-10 12:58:18

原文地址:面试题杂谈:体重和 作者:_Rayx

有n个人,要确定存不存在这样两个人,其体重和是112公斤, 能否找到一个O(N)的算法来解决此问题?有的话,说明算法是什么? 没有的话,说明原因,及最好的时间复杂度是多少?

现在大公司面试越来越多的考虑到算法方面的东西了,可能是对于产品来说一般技术壁垒太小了,核心就是比用户的忠诚度与产品的性能,而很多时候,性能与算法关系密切。

初看这题,一下子就能想到的就是对于每个人A,找一个B,B的体重是112-A就行了,这样复杂度是O(n^2)。

另一个解决方案是从找112-A这个地方来优化了,因为我们知道了A体重,有一个数组里找112-A可以二分查找,但二分查找要求有序,而排序复杂度可以为O(nlogn),这样查找的复杂度也是O(nlogn),总体复杂度还是O(nlogn),比上一个算法要好些。

还有没有更好的办法呢?对就是hash,对于hash来说查找一个元素为O(1),所以整体复杂度就是O(N)了。hash是个好办法,但是一下子要想到点上也不容易,如果题中说了体重是整数的话,那么很容易想到就是hash了,开一个112的数组,有体重在相应位置的人数加1即可,再枚举A体重,查找B体重。

所以觉得有时候就是这样,一个方法可以,换点东西其实用相同方法也可以,但是就是不能一下子想到点上。不知道还有没有其它更好的解决方案。


阅读(728) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~