请教一个算法问题

[luoluoluo]

对于数组A，B：
A = [a0, a1, ... , an-1]
B = [b1, b2, ..., bn-1]
有多少组i, j使得：
i < j && A[i] < B[j]

[bcxx]

@luoluoluo 不是 O(n^2) ...

[shoumu]

@glasslion 能详细说明一下吗，我没有想明白

[shoumu]

@xjx0524 直接排序的话有点问题吧
如：A = [1, 2, 3] B = [3, 2, 1] 满足条件数为1
A = [3, 2, 1] B = [1, 2, 3] 满足条件数为0

[bcxx]

@shoumu 要预先记录一下原下标

[joying]

时间复杂度O(nlogn)，先对两数组排序，后遍历A数组，对B数组进行二分查找，找到刚好比A[i]小的数的下标j，通过下标即可知道比A[i]大的B[j]的数量。

可以再优化，对B数组的二分查找不必从0开始，而是从刚好比A[i]小的B[j]开始。

[aheadlead]

记得有个很奇妙的方法可以做到 线性时间复杂度

[xjx0524]

@joying 哥们咱俩思路一样，但其实是错的，题目要求的不是任意i,j使得a[i]<b[j]，是要求i < j时 A[i] < B[j]，一排序就乱了。。。

[Exin]

不太明白你们为什么说排序……

我想角标和本身的值可以看做两个等价的属性，
那么排序前角标是有序的，排序后值是有序的，
那么排序应该是没有意义的。

能解释下吗？

[yangff]

不可能做到线性
如果让A=B
那么问题就变成求A的逆序对数
A的逆序对数的已知最优复杂度是O(nlgn)
故原问题复杂度不可能小过O(nlgn)

[joying]

@xjx0524 额。。。忽略了前面的i<j

[luoluoluo]

@bcxx Are you sure? Show me please.
@glasslion 那个对于一个数组理解，对于两个数组怎么操作？
@aheadlead 确定么？要是能找出来就好了哒
@yangff 树状数组能数细点么？
@xjx0524 ^_^
@joying ^_^

[aheadlead]

- - 好像看错了 是不是求逆序对啊...

[yangff]

@luoluoluo 窝系统挂了。。
你百度一下树状数组求逆序对，然后把查询比Ai小的变成查询比Bi小的就可以了

[wisatbff]

@xjx0524 带着下标一起排，没问题啊

[tideline]

这应该是一个稍作变形的逆序对问题吧，用树状数组写了一下，时间复杂度O(nlogn)，代码： http://paste.ubuntu.com/8071502/
这个版本的缺陷在于对数的大小有限制（数组里不能有负数和太大的数），可以离散化改进一下