Java——比较一长串整数

Question

我的代码超时了，因为它效率低下。程序接受一行n个整数。每对连续的整数代表一个点（x，y）。这是一个输入示例：

-5 -10 20 25 30 2 -1 -40

输出：

java.awt.Point[x=-5,y=-10]
java.awt.Point[x=-1,y=-40]
java.awt.Point[x=20,y=25]
java.awt.Point[x=30,y=2]
4

我有代码来排序所有的点。它们从最小到最大排序。如果"x"值相等，则检查y值。问题是：我需要计算一个点比其他点（x和y）大多少倍。所以在上面的例子中，答案是4。

>

第三点比第一点和第二点大。

结果是4。

如果点相等，也增加计数器。

对于非常长的整数行，我的程序超时（终止）。我不能在这里提供输入，因为它太长了。我还能如何提高复杂性？

public void calculateDomination(){
        int counter =0;
        int sizeOfList = this.coordinateList.size();
        for(int i = 0; i < sizeOfList ; i++){
            for(int j = i+1; j < sizeOfList ; j++){
                if(((this.coordinateList.get(i).x) < (this.coordinateList.get(j).x)) && ((this.coordinateList.get(i).y) < (this.coordinateList.get(j).y)) ){
                    counter++;
                }
                else if(((this.coordinateList.get(i).x) == (this.coordinateList.get(j).x)) && ((this.coordinateList.get(i).y) == (this.coordinateList.get(j).y)) ){
                    counter++;
                }
            }
        }
        System.out.println(counter);
    }

Answer 1

我发布的第一个想法现在被删除了，但实际上不起作用。真正起作用的是：

对遇到的y值进行增量排序/计数：

在浏览列表时，维护迄今为止遇到的所有y值的TreeMultiset。在每个点上，检查当前y值之前节点的headMultiset（）的size（）。由于只有x值较低的点的值会被添加到它，这将给出当前点的计数。

我认为TreeMultiset的所有相关操作都是O（log（n）），因此这将使算法从O（n^2）下降到O（n*log（n））。