请教一个算法问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3740 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

第 1 条附言 · 2014-08-17 15:11:18 +08:00

如果大家有什么好的解法，可以的话给出解法的__复杂度__和__解法的描述__。我很笨，希望能够听到比较__直白明了不失严谨__的表达，灰常感谢

第 2 条附言 · 2014-08-17 17:14:22 +08:00

首先灰常感谢大家热心答复，但不知是不是因为我没表达清楚，很多回答似乎没有理解题目意思。我的意思是：保证原始相对位置A里的在B里的前面的前提下，在数值上小于。我不是想知道仅仅在数值上有多少，相对位置要考虑。手机回复的，不及时还望见谅?

数组

请教

使得

35 条回复 • 2014-08-17 22:54:44 +08:00

em70

2014-08-17 13:32:07 +08:00

A,B数组长度相等吗

luoluoluo

2014-08-17 14:03:13 +08:00

@em70 等长，这个影响解法吗？

wisatbff

2014-08-17 14:07:19 +08:00

先排序，然后就不用说了吧

freetg

2014-08-17 14:08:03 +08:00

k=0
for i in xrange(n-1):
for j in xrange(i+1, n-1):
if A[i] < B[j]:
k += 1
print k

luoluoluo

2014-08-17 14:10:34 +08:00

@wisatbff 在下愚钝，请详述
@freetg 这个解法太过暴力

yangff

2014-08-17 14:11:09 +08:00 via Android

树状数组

wisatbff

2014-08-17 14:18:12 +08:00

@luoluoluo 排序之后和归并排序的“归并”操作类似

em70

2014-08-17 14:57:48 +08:00

遍历肯定可以解决,算法复杂度2^n,主要你希望简化到多少?

takato

2014-08-17 15:04:14 +08:00 via iPhone

O(nlogn)

luoluoluo

2014-08-17 15:06:37 +08:00

@yangff 数组数组是指数组区间维护最小值，查询的时候变快了，O(nlog(n))吗？

@wisatbff 是说按照数组值排序，再顺序往下归并，在依次比较下标吗？（如果我理解错了请说的在详细点，谢了哈）可是对于每个A的下标，B中可能存在不止一个下标符合，这样最坏的情形是不是O(n^2)

@em70 我希望可以降到O(n)

bcxx

2014-08-17 15:15:38 +08:00

@luoluoluo 试试可以将两个数组进行基排（或者其他 O(n) 的排序算法），然后再遍历两个数组，用类似归并排序的方法来逐个比较就可以了。这样就 O(n) 吧

xjx0524

2014-08-17 15:15:42 +08:00

两个数组分别排序O(nlog(n))
遍历A数组，对其中每个元素在B中二分，可以知道有多少比他大的
这样时间复杂度O(nlog(n))

bcxx

2014-08-17 15:21:15 +08:00

@bcxx 诶这里还说错了，应该是 O(n+k) 之类的排序算法……

xjx0524

2014-08-17 15:25:05 +08:00

@bcxx 仔细想了下，排序完之后可以O(n)统计结果，那样瓶颈就在排序了

GtDzx

2014-08-17 15:25:40 +08:00

线段树或者树状数组复杂度O(nlogn)
元素取值范围足够大的话，应该不存在O(n)算法。否则可以通过构造这类问题来O(n)解决n个元素排序问题。(这点我没想太仔细，不过感觉是上可以这样证明复杂度下限的 :P）

luoluoluo

2014-08-17 15:28:15 +08:00

@xjx0524 下标考虑了吗？

@bcxx 归并的话如我上面所说，如果B里面的数都大于A，最坏的情况是O(n^2)吧

xjx0524

2014-08-17 15:31:56 +08:00

@luoluoluo 和下标有什么关系？

归并那种方法，如果B里面的数都大于A，最坏的情况是O(2n)，省略常数就是O(n)

luoluoluo

2014-08-17 15:36:13 +08:00

@xjx0524
i<j && A[i]<B[i] 共有多少组组合满足，怎么和下标没关系呢？ i < j

xjx0524

2014-08-17 15:43:03 +08:00

@luoluoluo
我说的那种二分的方法，假设n为B数组元素个数
遍历A数组，拿a[i]在B中二分，找到位置使b[j]<=a[i]且b[j+1]>a[i]，那么总结果就加上n-j-1(如果数组索引从0开始)
对A数组中每个元素都这么做时间复杂度O(nlogn)

glasslion

2014-08-17 15:45:43 +08:00

keyword: 逆序数

bcxx

2014-08-17 15:51:18 +08:00

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

shoumu

2014-08-17 16:15:10 +08:00

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

shoumu

2014-08-17 16:17:41 +08:00

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

bcxx

2014-08-17 16:34:46 +08:00

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

joying

2014-08-17 16:58:19 +08:00

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

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

aheadlead

2014-08-17 17:38:20 +08:00 via iPhone

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

xjx0524

2014-08-17 17:50:06 +08:00

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

Exin

2014-08-17 17:52:10 +08:00

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

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

能解释下吗？

yangff

2014-08-17 17:58:12 +08:00 via Android

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

joying

2014-08-17 18:07:40 +08:00

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

luoluoluo

2014-08-17 19:34:12 +08:00

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

aheadlead

2014-08-17 19:35:37 +08:00

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

yangff

2014-08-17 20:48:54 +08:00 via Android

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

wisatbff

2014-08-17 21:11:18 +08:00

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

tideline

2014-08-17 22:54:44 +08:00

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