假设我有三个数组 a
, b
, 和 c
等长N
.这些数组中的每一个的元素都来自 totally ordered set , 但未排序。我还有两个索引变量,i
和 j
.对于所有 i != j
, 我想计算索引对的数量 a[i] < a[j]
, b[i] > b[j]
和 c[i] < c[j]
.有什么方法可以在小于 O(N ^ 2) 的时间复杂度内完成,例如创造性地使用排序算法?
注意:这道题的灵感是,如果你只有两个数组,a
和 b
, 你可以找到这样的索引对的数量 a[i] < a[j]
和 b[i] > b[j]
in O(N log N) with a merge sort .我基本上是在寻找对三个数组的概括。
为简单起见,您可以假设任何数组中没有两个元素是相等的(没有关系)。
最佳答案
通过对数组 a 进行排序并同时重新排列数组 b 和 c,我们可以假设 a[i] < a[j] <=> i < j。所以我们需要找到对 (i,j) 的数量,使得 i < j, b[i] > b[j] 和 c[i] < c[j]。让我们将 (b[i], c[i]) 视为平面上的一个点。我们一点一点地加分。每次我们添加一个点 (b[j], c[j]),首先我们计算已经添加的点 (i < j) 的数量,使得 b[i] > b[j] 和 c[i] < c [j].然后我们添加点 j 并继续下一个。每一步得到的数字之和就是我们的结果。
现在看来这种查询可以用二维线段树来完成:http://en.wikipedia.org/wiki/Segment_tree一次迭代的成本为 O(log^2 n),总复杂度为 O(n log^2 n)。
(请注意,我在这里假设数组的元素是数字。没关系,因为使用排序我们总是可以用从 1 到 n 的数字替换数组的元素,以便保留顺序。)
编辑:事实上,称为 Fenwick 树或二叉索引树的更简单的结构就足够了。请参阅此链接:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d
关于algorithm - 查找配对排序的有效方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4738780/