优化Codility中NumberOfDiscIntersections测试的性能方案咨询

问题背景 #

在平面上绘制N个圆盘，编号从0到N-1。给定非负整数数组A，A[J]为第J个圆盘的半径，其圆心位于坐标点(J, 0)。当J≠K且两个圆盘至少有一个公共点（包含边界）时，判定第J和第K个圆盘相交。
示例：当N=6，A=[1,5,2,1,4,0]时，共有11对相交圆盘。需实现Java函数class Solution { public int solution(int[] A); }，返回相交圆盘的无序对数，若数量超过10,000,000则返回-1。

我的实现代码 #

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
                Circle[] circleList = new Circle[A.length];
        //calculate left and right
        for(int i=0; i<A.length; i++) {
            int radius = A[i];
            Circle circle = new Circle();
            circle.setX(i);
            circle.setLeft(i-radius);
            circle.setRight(i+radius);
            circleList[i] = circle;
        }
        
        int intersection = 0;
        for(int i=0; i<A.length; i++) {
            //i+1 to avoid previously matched combination. i.e if i=2,j=1. this can //be excluded as it was already covered in i=1,j=2 
            for(int j=i+1; j<A.length; j++) {
                //System.out.println(i+" , "+j);
                Circle leftCir = circleList[i];
                Circle rightCircle = circleList[j];
                
                if(leftCir.right >= rightCircle.left) intersection++;
                
                if(intersection > 10000000) {
                    return -1;
                }
                
            }
        }
        
        return intersection;
    }

    static class Circle {
        int x;
        int left;
        int right;
        public int getX() {
            return x;
        }
        public void setX(int x) {
            this.x = x;
        }
        public int getRight() {
            return right;
        }
        public void setRight(int right) {
            this.right = right;
        }
        public int getLeft() {
            return left;
        }
        public void setLeft(int left) {
            this.left = left;
        }
        @Override
        public String toString() {
            return "Circle [x=" + x + ", left=" + left + ", right=" + right + "]";
        }
        
    }

}

遇到的问题 #

上述实现出现TIMEOUT超时错误，现咨询：

1. 如何优化该解法的性能？
2. 是否可以消除内层循环？
3. 该问题归类于排序类问题，如何利用排序算法解决？

问题解答 #

1. 性能优化思路 #

当前实现是O(N²)时间复杂度，当N达到10^5级别时必然超时。核心优化方向是将时间复杂度降至O(N log N)，核心是避免两两比对所有圆盘对，通过预处理和高效查找替代暴力遍历。

2. 可以消除内层循环 #

完全可以消除内层循环，通过「预处理边界数组+排序+二分查找」的组合方式，把双重循环的O(N²)操作转化为单次遍历加二分查找的O(N log N)操作，彻底规避暴力遍历的性能瓶颈。

3. 利用排序算法的解决方案 #

具体步骤如下：

• 预处理边界数组：生成两个数组，lefts存储每个圆盘的左边界（J - A[J]），rights存储每个圆盘的右边界（J + A[J]）。
• 排序左边界数组：对lefts数组进行升序排序，为后续二分查找做准备。
• 遍历计算相交对数：对于每个圆盘的右边界rights[i]，用二分查找找到lefts数组中第一个大于rights[i]的元素下标pos，那么前pos个元素对应的圆盘都和当前圆盘相交。再减去i+1（排除当前圆盘和之前已统计过的配对，避免重复计数），得到新增的相交对数。

对应的Java实现代码：

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        int n = A.length;
        long[] lefts = new long[n];
        long[] rights = new long[n];
        
        // 预处理左右边界，用long避免整数溢出
        for (int i = 0; i < n; i++) {
            lefts[i] = (long)i - A[i];
            rights[i] = (long)i + A[i];
        }
        
        Arrays.sort(lefts);
        
        long count = 0;
        for (int i = 0; i < n; i++) {
            // 二分查找第一个大于rights[i]的位置
            int low = 0, high = n;
            while (low < high) {
                int mid = (low + high) / 2;
                if (lefts[mid] > rights[i]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            // 新增的相交对数 = 所有左边界<=当前右边界的数量 - 已统计过的配对（i+1个）
            count += low - (i + 1);
            if (count > 10000000) {
                return -1;
            }
        }
        
        return (int)count;
    }
}

关键说明：

• 使用long类型是为了避免大数值溢出（比如当i和A[i]都很大时，i+A[i]会超出int范围）。
• 二分查找的时间复杂度为O(log N)，遍历为O(N)，总时间复杂度O(N log N)，可处理大规模输入。
• 计算low - (i+1)是为了避免重复计数：前i个圆盘已经和当前圆盘完成配对统计，只需统计后续未配对的圆盘数量。

内容的提问来源于stack exchange，提问作者Renjith