Java 为整数的平方根编写程序时出现堆 Space 错误

Question

我试图找出一个整数的平方根，但万一整数值太大，例如 - 2147395599。然后下面的程序给出了这个异常。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at com.aakash.BinarySearch.SquareRoot.mySqrt(SquareRoot.java:12)
    at com.aakash.BinarySearch.SquareRoot.main(SquareRoot.java:8)

Process finished with exit code 1

平方根程序

package com.aakash.BinarySearch;

import java.util.Arrays;

public class SquareRoot {

    public static void main(String[] args) {
            int ans = mySqrt(2147395599);
        System.out.println(ans);
    }
    public static int mySqrt(int x) {
        int[] arrayUpton = new int[x];
        int start =0;
        int end = arrayUpton.length-1;
        int mid =  start + (start-end)/2;

        for (int index = start; index <= end; index++) {
            arrayUpton[index]=index+1;
        }

        for (int index = start; index < end; index++) {
            if(arrayUpton[index]*arrayUpton[index]==x){
                return arrayUpton[index];
            } else if (arrayUpton[index]*arrayUpton[index]>x) {
                return arrayUpton[index-1];
            }
        }
        return 0;
    }

}

Answer 1

您正试图分配一个包含近 2^31 个整数的数组。这将占用 8GB，这（显然）对于您的 JVM 堆来说太大了。（而且它可能对您的计算机来说太大了。）

但你真正的问题是你的算法。

您不需要分配一个巨大的数组来计算整数平方根。即使您通过搜索所有（正）int 值来做到这一点。

考虑一下：您的代码小心地将每个数组元素设置为比数组下标大 1 的数字。然后它从数组中检索值以使用它们。但是，如果您知道 arrayUpton[i] 包含 i + 1 ...，则无需检索它。只需将 1 添加到 i 而不是从数组中获取（相同的）值。

另外：

不管标签如何，您的算法都没有实现二进制搜索。
我什至不相信该算法会起作用。

我建议你谷歌一下，看看能不能找到更好的整数平方根算法。

Java 为整数的平方根编写程序时出现堆 Space 错误

Java Heap Space error while writing a program for Square root of an Integer

java

binary-search