java - 低效的 java/未知长度的数组

Question

我正在制作一些用于查找某个数的质因数的方法。这被分解为两个都使用数组的函数。但是，在这两个函数中，代码都非常低效。首先，我必须计算数组的长度，创建一个具有该长度的新数组，然后使用几乎完全相同的代码来填充该数组。

有没有办法让数组的宽度未知，并在找到整数时将其推到数组的末尾？

这是我的代码:

public class JavaApplication7{
    public static void main(String[] args) {
        System.out.println(Arrays.toString(primeFactors(85251)));
    }
    public static int[] primeFactors(int num){
        int[] factors = primesUpTo(num);
        int originalNum = num;
        int i = 0;
        int count = 0;
        while(num != 1){
            if(num % factors[i] == 0){
                num /= factors[i];
                i = 0;
                count++;
            }else{
                i++;
            }
        }
        int[] primeFactors = new int[count];
        i = 0;
        count = 0;
        while(originalNum != 1){
            if(originalNum % factors[i] == 0){
                originalNum /= factors[i];
                primeFactors[count] = factors[i];
                i = 0;
                count++;
            }else{
                i++;
            }
        }
        return primeFactors;
    }
    public static int[] primesUpTo(int upTo){
        int count = 0;
        int num = 2;
        while(num <= upTo){
            boolean isPrime = true;
            for(int div = 2; div <= num / 2; div++){
                isPrime = num % div == 0 ? false : isPrime;
            }
            count += isPrime ? 1 : 0;
            num++;
        }
        int i = 0;
        num = 2;
        int[] primes = new int[count];
        while(num <= upTo){
            boolean isPrime = true;
            for(int div = 2; div <= num / 2; div++){
                isPrime = num % div == 0 ? false : isPrime;
            }
            if(isPrime){
                primes[i] = num;
                i++;
            }
            num++;
        }
        return primes;
    }    
} 

Answer 1

您可以使用比数组更动态的数组列表。

However in both functions the code is very inefficient as first i have to count the length of the array, make a new array of that length and then use almost the exact same code to populate the array

但是，您会发现 Arraylists 看起来确实是动态的，但实际上它们在做类似的事情。它们从一个大小开始，然后将底层 Array 复制到一个更大的数组等。

如果您知道必须存储的数字的上限，您可以做的另一件事是实现您自己的容器类。它可以有一个大数组来保存数字和一个长度变量，用于遍历元素。

例如:

public class NumberContainer(){

    private int[] elements;
    private int numOfElements;

    public NumberContainer(int size){
        elements = new int[size];
        numOfElements = 0;
    }

    //add a number

    public void add(int x){
        elements[numOfElements] = x;
        numOfElements++;
    }

    //get length
    public int length(){
        return numOfElements;
    }

}

....等等。

这样您就不必将 Array 复制到一个新的大数组，始终假设您实例化了具有足够大大小的 NumberContainer。

希望对你有帮助