給定一組n個點（x，y），是否有可能在O（n logn）時間內找到它們之間具有負斜率的點對的數量？

Question

給定一個形式爲(x,y)的二維平面上的n個點的集合，目標是找到所有點的對的數目(xi,yi)和(xj, yj)，使得連接兩個點的線具有負斜率。

假設沒有兩個xi具有相同的值。假設所有點位於[-100,100]或其他一些範圍內。

Answer 1

你在問什麼等於找到y的數組中的非反轉數，當你將這些點相對於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）。您可以看到，負斜率由（3,1），（3，3），（012），（2,1），（4，4），<（2,1），（5,2） >，<（2,1），（6,6）>等所有的對，其中y不在倒置。

使用合併排序算法的增量可以在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。