一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1002|回复: 22
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
fame 发表于 2016-3-18 07:02:24 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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.还有更好的方法吗?

adiggo 发表于 2016-3-18 07:24:11 | 显示全部楼层
这个 只能n^2吧。 因为你输出的情况最多应该就有n^2/2 吧。
回复 支持 反对

使用道具 举报

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是两个数组共有的元素数
抛个砖~
回复 支持 反对

使用道具 举报

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?
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-3-20 01:47:47 | 显示全部楼层
colastar 发表于 2016-3-19 15:13
如果用merge sort去找逆序对,那么找到逆序对后,要找到最后的结果应该要有一个O(M)的花费吧,M指得是逆 ...

每次递归除了count还会返回一个sortedlist,所以复杂度和mergesort是一样的,和m没有关系
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-3-20 01:50:07 | 显示全部楼层
iwofr 发表于 2016-3-19 00:44
这个是merge sort的一个应用count inverted pairs,搜一下,挺有名的,nlogn。

我感觉不太一样吧?mergesort这个是找和有序序列的逆序对,这个题是找和任意序列,方法感觉不能移植过来吧,请指教
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-3-20 01:50:51 | 显示全部楼层
ryancooper 发表于 2016-3-18 14:09
如果只是统计pair的数量的话,可以nlogn

我感觉不太一样吧?nlogn是找和有序序列的逆序对数量吧,这个题是找和任意序列,方法感觉不能移植过来吧,请指教
回复 支持 反对

使用道具 举报

colastar 发表于 2016-3-20 13:13:15 | 显示全部楼层
bbsbbstry 发表于 2016-3-20 01:47
每次递归除了count还会返回一个sortedlist,所以复杂度和mergesort是一样的,和m没有关系

我的意思是,你找到了sortedlist后,是需要比较两个数组的sorted list才能得到最后的结果。。
回复 支持 反对

使用道具 举报

colastar 发表于 2016-3-20 13:14:57 | 显示全部楼层
bbsbbstry 发表于 2016-3-20 01:47
每次递归除了count还会返回一个sortedlist,所以复杂度和mergesort是一样的,和m没有关系

难道题目的意思是只对A2数组做?-_-#
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-3-20 13:26:43 | 显示全部楼层
bbsbbstry 发表于 2016-3-20 01:50
我感觉不太一样吧?nlogn是找和有序序列的逆序对数量吧,这个题是找和任意序列,方法感觉不能移植过来吧 ...

为啥不能,你实际要对第二个数组按照有第一个数组定义的元素之间的偏序关系来进行排序,在排序过程中不就可以统计逆序对的个数吗
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-3-20 13:57:23 | 显示全部楼层
ryancooper 发表于 2016-3-20 13:26
为啥不能,你实际要对第二个数组按照有第一个数组定义的元素之间的偏序关系来进行排序,在排序过程中不就 ...

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

使用道具 举报

bbsbbstry 发表于 2016-3-20 13:58:37 | 显示全部楼层
ryancooper 发表于 2016-3-20 13:26
为啥不能,你实际要对第二个数组按照有第一个数组定义的元素之间的偏序关系来进行排序,在排序过程中不就 ...

你有什么更好的方法实现么?
回复 支持 反对

使用道具 举报

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里~就完了啊~
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-3-20 23:13:38 | 显示全部楼层
bbsbbstry 发表于 2016-3-20 01:50
我感觉不太一样吧?mergesort这个是找和有序序列的逆序对,这个题是找和任意序列,方法感觉不能移植过来 ...

什么是有序序列?要是都有序了为了啥还有逆序对?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 09:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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