给定形式为 的二维平面上的一组 n 个点(x,y)，目标是找到所有点的对数，(xi,yi)并且(xj, yj)使连接两个点的线具有负斜率。
假设没有两个xi具有相同的值。假设所有点都在[-100,100]或某个其他范围内。
问问题
590 次
1 回答
8
y您要问的问题相当于在对s 的点进行排序时将获得的 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。
于 2013-05-08T07:59:33.780 回答