下面是一个面试问题，我已经尽力解决了。所需的界限应小于O(n^2)问题是：
给你一组点S=(x1,y1)....(xn,yn)要点
是xy平面上的坐标。有一点被认为是
大于点(xa,ya)当且仅当(xb,yb)和xa > xb时。
目标是从集合s中找到p1=（xa，ya）和p2=（xb，yb）的所有点对，使得p1>p2。
例子：
Input S = (1,2),(2,1),(3,4)
Answer: {(3,4),(1,2)} , {(3,4),(2,1)}
我只能想出一个
ya > yb解决方案，其中包括相互检查每个点如果有更好的方法，请帮助我。 最佳答案
我想你是真的想数这样的一对。
按x中的O(n log n)向下排序。现在我们将问题简化为一个一维：对于每个位置k我们需要在它大于位置k处的数字之前计算出多少个数字这相当于计算倒数，这个问题在这个网站上已经被多次回答，包括我，例如here。
要获得这个问题的O(n log n)最简单的方法是使用合并排序算法，如果您想在单击该链接之前自己考虑它的话。其他方法包括使用二进制索引树（fenwick树）或二进制搜索树。实践中最快的可能是使用二进制索引树，因为它们只涉及按位操作。
如果您想打印对，在最坏的情况下，您不能比O(n^2)做得更好。不过，我也会对输出敏感的O(num_pairs)算法感兴趣。