Java中寻找原点与半径外最近整数坐标的性能优化问题

给定整数半径r，需找到整数坐标(x, y)，满足：

• 该点到原点的距离严格大于r
• 这个距离是所有满足条件的点中最小的

当前Java代码在r≤5000时运行正常，但r≥10000时耗时呈指数级增长，需要优化方案。

示例：

• r=1 → (1,1)
• r=5 → (2,5)
• r=10 → (5,9)

当前代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class disc_district {

    public static void main(String[] args) {
        
        Scanner new_scanner = new Scanner(System.in);

        int radius = new_scanner.nextInt();
        new_scanner.close();

        //ArrayList<Double> new_distance = new ArrayList<>();

        double min_max_dist = Double.MAX_VALUE - 1;
        int[] new_min_pair = new int[2];

        for (int i = (radius / 2); i <= radius; i++) {
            int start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2))) + 1;
            for (int j = Math.max(i, start); j <= radius; j++) {
            //for (int j = i; j <= radius; j++) {
                double new_dist = Math.sqrt(Math.pow(i, 2) + Math.pow(j, 2));

                if (new_dist > radius) {
                    if (min_max_dist > new_dist) {
                        min_max_dist = new_dist;
                        new_min_pair[0] = i;
                        new_min_pair[1] = j;
                    }
                }
            }
        }
        System.out.println(new_min_pair[0] + " " + new_min_pair[1]);
    }
}

1. 替换浮点运算为整数比较 #

浮点运算既慢又容易出现精度误差，直接比较距离的平方即可——平方运算不会改变大小关系：

• 原条件new_dist > radius等价于i² + j² > r²
• 寻找最小距离等价于寻找最小的i² + j²且满足i² + j² > r²

这样可以彻底移除Math.sqrt和Math.pow的调用，大幅提升计算效率。

2. 大幅缩小遍历范围 #

最优解的坐标一定在r附近，不需要从radius/2开始遍历。可以把i的起始点设为max(0, r - 200)（200是足够覆盖最优解的缓冲值，实际还可以更小），因为离r太远的点，其距离平方必然比r附近的点大，不可能成为最优解。

3. 提前终止无效循环 #

• 外层循环：当2*i² >= 当前找到的最小平方和时，直接跳出循环——因为j≥i，后续的i²+j²只会更大，不可能得到更优解。
• 内层循环：一旦i²+j² >= 当前找到的最小平方和，立即终止遍历——j递增的情况下，后续值只会让平方和更大，无需继续计算。

优化后的代码 #

import java.util.Scanner;

public class disc_district {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int r = scanner.nextInt();
        scanner.close();

        long rSq = (long) r * r;
        long minSq = Long.MAX_VALUE;
        int bestX = 0, bestY = 0;

        // 只遍历r附近的范围，覆盖最优解足够
        int startI = Math.max(0, r - 200);
        for (int i = startI; i <= r; i++) {
            long iSq = (long) i * i;
            // 提前终止：i和i的平方和已经不小于当前最小值，后续j>=i只会更大
            if (2 * iSq >= minSq) {
                break;
            }
            // 计算j的最小起始值：满足i²+j²>r²的最小j，且j>=i
            int minJ = (int) Math.ceil(Math.sqrt(rSq - iSq)) + 1;
            minJ = Math.max(minJ, i);
            // 内层循环，提前终止无效计算
            for (int j = minJ; j <= r; j++) {
                long currentSq = iSq + (long) j * j;
                if (currentSq >= minSq) {
                    break;
                }
                // 更新最优解
                minSq = currentSq;
                bestX = i;
                bestY = j;
            }
        }

        System.out.println(bestX + " " + bestY);
    }
}

优化效果说明 #

优化后的代码时间复杂度从O(r²)降到近似O(1)（因为只遍历r附近的固定范围），即使r=1e5也能瞬间出结果，同时避免了浮点运算的精度问题。

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