计算数字交叉盘的

Question

请参阅此问题和接受的答案：

Algorithm to calculate number of intersecting discs

而不是使用二叉树的，如果你是使用一个数组，排序，然后只需通过遍历了数组？它仍然是O（n log n）吗？

通过迭代数组排序（我）似乎将是为O（n^2）....

Answer 1

接受的答案谈到二进制搜索在排序后的数组，不约二进制树。二进制搜索是logn，“简单迭代”是n。所以你会真的做出解决方案O(n^2)。但对数组进行简单迭代没有意义，您知道该数组已排序 - 您可以使用二分搜索。