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

colastar 发表于 2016-3-19 15:13
如果用merge sort去找逆序对，那么找到逆序对后，要找到最后的结果应该要有一个O（M）的花费吧，M指得是逆 ...

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

iwofr 发表于 2016-3-19 00:44
这个是merge sort的一个应用count inverted pairs，搜一下，挺有名的，nlogn。

我感觉不太一样吧？mergesort这个是找和有序序列的逆序对，这个题是找和任意序列，方法感觉不能移植过来吧，请指教

ryancooper 发表于 2016-3-18 14:09
如果只是统计pair的数量的话，可以nlogn

我感觉不太一样吧？nlogn是找和有序序列的逆序对数量吧，这个题是找和任意序列，方法感觉不能移植过来吧，请指教

bbsbbstry 发表于 2016-3-20 01:47
每次递归除了count还会返回一个sortedlist，所以复杂度和mergesort是一样的，和m没有关系

我的意思是，你找到了sortedlist后，是需要比较两个数组的sorted list才能得到最后的结果。。

bbsbbstry 发表于 2016-3-20 01:47
每次递归除了count还会返回一个sortedlist，所以复杂度和mergesort是一样的，和m没有关系

难道题目的意思是只对A2数组做？-_-#

bbsbbstry 发表于 2016-3-20 01:50
我感觉不太一样吧？nlogn是找和有序序列的逆序对数量吧，这个题是找和任意序列，方法感觉不能移植过来吧 ...

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

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

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

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

你有什么更好的方法实现么？

colastar 发表于 2016-3-20 13:13
我的意思是，你找到了sortedlist后，是需要比较两个数组的sorted list才能得到最后的结果。。

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

bbsbbstry 发表于 2016-3-20 01:50
我感觉不太一样吧？mergesort这个是找和有序序列的逆序对，这个题是找和任意序列，方法感觉不能移植过来 ...

什么是有序序列？要是都有序了为了啥还有逆序对？