编写整数平方根程序时出现Java堆空间错误

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值来实现。

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

此外：

• 你的算法没有实现二进制搜索。我甚至不相信它会起作用
• 我建议你用谷歌搜索一下，看看是否能找到更好的算法