将元素添加到整数数组的开头

Question

使用 addBefore() 方法，将新元素添加到 int 数组的开头，然后使现有元素的索引增加一。

这是尝试运行时控制台中显示的内容——java.lang.RuntimeException: Index 1 应该有值 11 但在 IntArrayListTest.main(IntArrayListTest.java:67) 处有 0

以下是我到目前为止的代码。

public class IntArrayList {

private int[] a; 

private int length;

private int index;

private int count;

public IntArrayList() {

    length = 0; 

    a = new int[4]; 

}

public int get(int i) { 

    if (i < 0 || i >= length) {

        throw new ArrayIndexOutOfBoundsException(i);

    }

    return a[i];

}

public int size() { 

    return length; 

}

public void set(int i, int x) {

    if (i < 0 || i >= a.length) {

        throw new ArrayIndexOutOfBoundsException(i);

    }

    a[i] = x;

}

public void add(int x) {

    if (length >= a.length) {

        int[] b = new int[a.length * 2];

        for (int i = 0; i < a.length; i++) {

            b[i] = a[i];

        }

        a = b;

        //count += 1;

    }

    a[length] = x;

    count++;

    length = length + 1;

}

public void addBefore(int x) {

    int[] b = new int[a.length*2];

    for (int i = 0; i < a.length; i++) {

        b[i+a.length] = a[i];

    }

    a = b;

    a[index] = x;

    length ++;

    }   

}

Answer 1

如果答案要求您自己进行循环，那么这样的事情应该可以正常工作（执行此操作的几种方法之一，但是是O(n)）：public void addBefore(int x) {&nbsp; &nbsp; &nbsp; &nbsp; if(length + 1 >= a.length){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] b = new int[a.length*2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[0] = x;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[i + 1] = a[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a = b;&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = length; i >= 0 ; i--) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[i + 1] = a[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[0] = x;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; length++;&nbsp; &nbsp; }我注意到这开始运行“速度测试” - 不确定这样的测试有多有用，因为它将基于 cpu 性能，而不是测试算法的复杂性..

Answer 2

无论您是先添加还是最后添加，只有在数组已满时才需要增加数组大小。该count字段似乎与 完全相同length，并且index作为一个字段似乎未使用且无意义，因此将它们都删除。要重新排列数组中的值，请使用以下方法：System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)你的两个“添加”方法应该是：public class IntArrayList {&nbsp; &nbsp; private int[] a; // Underlying array&nbsp; &nbsp; private int length; // Number of added elements in a&nbsp; &nbsp; // other code&nbsp; &nbsp; public void add(int x) {&nbsp; &nbsp; &nbsp; &nbsp; if (length == a.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] b = new int[a.length * 2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(a, 0, b, 0, length);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a = b;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; a[length++] = x;&nbsp; &nbsp; }&nbsp; &nbsp; public void addBefore(int x) {&nbsp; &nbsp; &nbsp; &nbsp; if (length < a.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(a, 0, a, 1, length);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] b = new int[a.length * 2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(a, 0, b, 1, length);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a = b;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; a[0] = x;&nbsp; &nbsp; &nbsp; &nbsp; length++;&nbsp; &nbsp; }}

Answer 3

您的解决方案存在三个问题：您增加了a每次调用该方法的长度。这将很快创建一个OutOfMemoryException当你从ato复制值时b，你做了b[i+a.length] = a[i];这意味着这些值将被复制到中间b而不是只移动一个位置最后，您将新值放在数组的末尾而不是开头。我之所以能看到这一切，是因为我在您的代码上使用了调试器。如果您希望能够检测和修复代码中的问题，则需要开始使用此工具。所以固定的解决方案会这样做：检查是否a已满（就像使用add()方法完成一样），如果是，则创建b并将所有内容复制到其中，依此类推）将所有值前移一位。最简单的方法是从长度向后循环到0在数组的开头分配新值这是一个可行的解决方案：public void addBefore(int x) {&nbsp; &nbsp; // increase length if a is full&nbsp; &nbsp; if (length >= a.length) {&nbsp; &nbsp; &nbsp; &nbsp; int[] b = new int[a.length * 2];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < a.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[i] = a[i];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; a = b;&nbsp; &nbsp; }&nbsp; &nbsp; // shift all values one cell ahead&nbsp; &nbsp; for (int i = length; i > 0; i--) {&nbsp; &nbsp; &nbsp; &nbsp; a[i] = a[i-1];&nbsp; &nbsp; }&nbsp; &nbsp; // add new value as first cell&nbsp;&nbsp; &nbsp; a[0] = x;&nbsp; &nbsp; length ++;&nbsp; &nbsp; }&nbsp; &nbsp;}