📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3313| 回复: 22
跳转到指定楼层
上一主题 下一主题
收起左侧

Google算法题,有比O(n^2)更好的算法吗?

🔗
fame | 只看该作者 |倒序浏览
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
There are two arrays A1 and A2. Find out the pairs of numbers in A2 which were in reverse order
in A1. For example, A1 = [2 6 5 8 1 3], A2 = [1 2 3 4 5 6]. Answer: (1, 2), (1, 5), (1, 6), (5, 6), (3, 5), (3, 6).


O(n^2)的算法就是用hash记录第一个数组里面的位置,然后双循环A2.还有更好的方法吗?


上一篇:地里有C++ code review的组嘛?
下一篇:问道题:一张纸折起来的面积
推荐
bbsbbstry 2016-3-20 13:57:23 | 只看该作者
全局:
ryancooper 发表于 2016-3-20 13:26
为啥不能,你实际要对第二个数组按照有第一个数组定义的元素之间的偏序关系来进行排序,在排序过程中不就 ...

偏序关系定义这个算法是没问题的,我就是觉得从这道题面试coding的角度这样很蛋疼。我能想到的最好的实现就是先把两个数组都存在的元素从数组2里hash出来,然后用数组一的值做key,index做value建哈希表,用这个表写comparator里的compare函数,然后才能继续写这个算法,这还得建立在数组元素没有重复的基础上,不然更麻烦。。。
回复

使用道具 举报

推荐
Adeath 2016-3-18 07:43:03 | 只看该作者
全局:
Worst case n^2 肯定的吧 比如[5 4 3 2 1] 和 [1 2 3 4 5].  感觉只能稍微优化一下
假设array内没有duplicate, 可以把A1和A2都存哈希表,先找出A1各数在A2中的位置 比如
2 6 5 8 1 3
1 5 4 x 0 2   x代表没有 不必考虑
然后 check 所有的pair是不是valid
这样可以优化到 O(m^2) m是两个数组共有的元素数
抛个砖~
回复

使用道具 举报

推荐
bbsbbstry 2016-3-20 14:08:02 | 只看该作者
全局:
colastar 发表于 2016-3-20 13:13
我的意思是,你找到了sortedlist后,是需要比较两个数组的sorted list才能得到最后的结果。。

没懂你的意思,有sortedlists之后就递归树的每层都是一个O(n)的合并了啊,一共log(n)层,这过程中出现数组1元素大于数组2元素时直接把1的后半段加进count里~就完了啊~
回复

使用道具 举报

🔗
adiggo 2016-3-18 07:24:11 | 只看该作者
全局:
这个 只能n^2吧。 因为你输出的情况最多应该就有n^2/2 吧。
回复

使用道具 举报

🔗
carthus 2016-3-18 08:13:56 | 只看该作者
全局:
Adeath 发表于 2016-3-18 07:43
Worst case n^2 肯定的吧 比如[5 4 3 2 1] 和 [1 2 3 4 5].  感觉只能稍微优化一下
假设array内没有dupli ...

讨论复杂度就是讨论最坏情况吧,复杂度还是n^2
回复

使用道具 举报

🔗
Adeath 2016-3-18 12:56:31 | 只看该作者
全局:
carthus 发表于 2016-3-18 08:13
讨论复杂度就是讨论最坏情况吧,复杂度还是n^2

那不一定 举例来说QuickSort最坏就是n^2 但average是 nlogn
回复

使用道具 举报

🔗
ryancooper 2016-3-18 14:09:05 | 只看该作者
全局:
如果只是统计pair的数量的话,可以nlogn
回复

使用道具 举报

🔗
 楼主| fame 2016-3-19 00:35:28 | 只看该作者
全局:
ryancooper 发表于 2016-3-18 14:09
如果只是统计pair的数量的话,可以nlogn

能详细说说吗?
回复

使用道具 举报

🔗
iwofr 2016-3-19 00:44:44 | 只看该作者
全局:
这个是merge sort的一个应用count inverted pairs,搜一下,挺有名的,nlogn。
回复

使用道具 举报

🔗
 楼主| fame 2016-3-19 04:21:41 | 只看该作者
全局:
iwofr 发表于 2016-3-19 00:44
这个是merge sort的一个应用count inverted pairs,搜一下,挺有名的,nlogn。

找到了,谢谢!

http://www.geeksforgeeks.org/counting-inversions/
回复

使用道具 举报

🔗
colastar 2016-3-19 15:13:26 | 只看该作者
全局:
如果用merge sort去找逆序对,那么找到逆序对后,要找到最后的结果应该要有一个O(M)的花费吧,M指得是逆序对的数量。这个M可能有些大,会超过NLOGN?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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