ash*_*p21 9 algorithm divide-and-conquer computational-geometry
给定形式的2维平面上的一组n个点(x,y),目的是找到所有点的对的数量,(xi,yi)并且(xj, yj)使得连接这两个点的线具有负斜率.
假设没有两个xi人具有相同的价值.假设所有点都在[-100,100]或在其他范围内.
你要问的是相当于y在你对点进行排序时你将获得的s 数组中的非反转次数x.你可以负担这种分类 - 它是O(n log n).
我提醒你,反转是i> j和a[i]< a[j].我所说的等价很容易证明.
想象一下,你有6分(4,4),(2,1),(6,6),(3,3),(5,2),(1,5).在对你进行排序后,x你得到:(1,5),(2,1),(3,3),(4,4),(5,2),(6,6).您可以看到负斜率由<(2,1),(3,3)>,<(2,1),(4,4)>,<(2,1),(5,2)形成>,<(2,1),(6,6)>等.所有ys都没有反转的对.
O(n log n)使用合并排序算法的增量可以计算反转次数:基本上,每次选择添加右子阵列的值(包含较大索引的值)时,您只需要增加反转计数器.您可以使用左子阵列中仍未处理的值来增加反转次数.
以下是计算反转次数的示例.
Initial array 5 1 3 4 2 6 inv := 0 // Total inversions: 6
merge step 1: <5 1 3> <4 2 6> inv = 0
merge step 2: <5> <1 3> | <4> <2 6> inv = 0
merge step 3: <5> [<1> <3>] | <4> [<2> <6>] inv = 0
merge step 4: <5> <1 3> | <4> <2 6> inv = 0 // both pairs were already sorted
merge step 5: <1 3 5> | <2 4 6> inv = 3 // we add one for 1, 3 and 2
merge step 6 <1 2 3 4 5 6> inv = 6 // we add 2 (3 and 5) for 2 and 1 for 4
在您找到反转次数后,总对数中的非反转次数(n * (n - 1)) / 2减去反转次数inv.
在示例中,这是:6 * 5 / 2 - 6 = 9.