寄托天下
查看: 1663|回复: 3
打印 上一主题 下一主题

[技术问答] 准备面试问这个题目各位看看 [复制链接]

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
882

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

跳转到指定楼层
楼主
发表于 2011-4-21 01:24:04 |只看该作者 |倒序浏览
职位:Java Dev

输入,List<Point>

Point是一个平面坐标系上的点

求该list中的3点,以其为顶点构成的三角形面积最大。

该list很大,要求一个高效的算法。

写一个程序。Point要自己实现。
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK
回应
0

使用道具 举报

Rank: 11Rank: 11Rank: 11Rank: 11

声望
3110
寄托币
48275
注册时间
2003-9-1
精华
44
帖子
1501

荣誉版主 GRE斩浪之魂 Golden Apple

沙发
发表于 2011-4-21 09:18:17 |只看该作者
没想到啥好算法。。。挫人飘过。。。

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
882

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

板凳
发表于 2011-4-21 10:24:24 |只看该作者
直接想到的是先求凸包,非凸包上的点删掉,然后。。。。先枚举着
soonyu 发表于 2011-4-21 09:27


凸包O(nlogn),凸包后,如果在做凸包时就把点排号,可以O(n)
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
882

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

地板
发表于 2011-4-21 10:25:21 |只看该作者
因为我可以把所有点都放在凸包上,这样你枚举的最坏情况就是O(n^3)了
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK

使用道具 举报

RE: 准备面试问这个题目各位看看 [修改]
您需要登录后才可以回帖 登录 | 立即注册

问答
Offer
投票
面经
最新
精华
转发
转发该帖子
准备面试问这个题目各位看看
https://bbs.gter.net/thread-1257438-1-1.html
复制链接
发送
报offer 祈福 爆照
回顶部