找到"平衡"点的算法

Question

我在以下任务中发现比O(n ^ 2)更复杂的问题:

"当a1> b1 && a2> b2 && ... && a> bn时,我们说点A =(a1,a2,...,an)支配B =(b1,b2,...,bn).我们给出一组点S并且需要返回一个点的索引,该点占主导地位并且由相同数量的点(平衡点)支配,或者如果不存在这样的点,则返回-1.

int findBalancePoint(Point[] S, int n){
    int index = 0;
    int dominates, isDominated;

    for(int i = 0; i < n; i++){
        index = i;
        swap(S, 0, i);
        dominates = isDominated = 0;
        for(int j = 1; j < n; j++){
            if( S[0].x > S[j].x && S[0].y > S[j].y )
                dominates++;
            else if( S[0].x < S[j].x && S[0].y < S[j].y )
                isDominated++;
        }
        if(dominates == isDominated)
            return index;
    }

    return -1;
}

由于这是算法测试之前的一个示例练习,我猜有更好的解决方案.在此先感谢您的帮助.

更新

测试:

Input1: (1,2), (2,1), (3,3), (4,4), (5,6)
Result: 2

Input2: (1,1), (3,2), (4,5)
Result: 1

Input3: (1,4), (2,3), (3,1), (4,2)
Result: 0 or 1 ( doesnt matter which one )

Input4: (1,1), (2,2), (3,3), (4,4)
Result: -1

Input5: (1,2), (2,1), (3,3), (3,5), (4,4), (5,6), (6,2)
Result: 2 or 3

Answer 1

一种想法是按照 x 坐标递增的顺序访问这些点。

当您访问每个点时，您将其 y 坐标插入平衡二叉树中（每个点的复杂度为 O(logn)）。

您还查询二叉树以找到 y 值较小的点数，这就是它占主导地位的点数。

然后，您可以按 x 坐标递减的顺序重复此过程，以找到每个点所主导的点的数量。

总的来说，我相信这给出了 O(nlogn) 复杂度。

更新

正如 Julian 在评论中指出的那样，如果有多个点具有相同的 x 坐标，则此解决方案将失败。解决此问题的方法是，在将这些点添加到二叉树之前，对具有相同 x 坐标的点进行所有查询。