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

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) {

        if(length + 1 >= a.length){

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

            b[0] = x;

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

                b[i + 1] = a[i];

            }

            a = b;

        } else {

            for (int i = length; i >= 0 ; i--) {

                a[i + 1] = a[i];

            }

            a[0] = x;

        }

        length++;

    }

我注意到这开始运行“速度测试” - 不确定这样的测试有多有用，因为它将基于 cpu 性能，而不是测试算法的复杂性..

Answer 2

无论您是先添加还是最后添加，只有在数组已满时才需要增加数组大小。

该count字段似乎与 完全相同length，并且index作为一个字段似乎未使用且无意义，因此将它们都删除。

要重新排列数组中的值，请使用以下方法：

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

你的两个“添加”方法应该是：

public class IntArrayList {

    private int[] a; // Underlying array

    private int length; // Number of added elements in a

    // other code

    public void add(int x) {

        if (length == a.length) {

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

            System.arraycopy(a, 0, b, 0, length);

            a = b;

        }

        a[length++] = x;

    }

    public void addBefore(int x) {

        if (length < a.length) {

            System.arraycopy(a, 0, a, 1, length);

        } else {

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

            System.arraycopy(a, 0, b, 1, length);

            a = b;

        }

        a[0] = x;

        length++;

    }

}

Answer 3

您的解决方案存在三个问题：

1. 您增加了a每次调用该方法的长度。这将很快创建一个OutOfMemoryException

2. 当你从ato复制值时b，你做了b[i+a.length] = a[i];这意味着这些值将被复制到中间b而不是只移动一个位置

3. 最后，您将新值放在数组的末尾而不是开头。

我之所以能看到这一切，是因为我在您的代码上使用了调试器。如果您希望能够检测和修复代码中的问题，则需要开始使用此工具。

所以固定的解决方案会这样做：

1. 检查是否a已满（就像使用add()方法完成一样），如果是，则创建b并将所有内容复制到其中，依此类推）

2. 将所有值前移一位。最简单的方法是从长度向后循环到0

3. 在数组的开头分配新值

这是一个可行的解决方案：

public void addBefore(int x) {

    // increase length if a is full

    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;

    }

    // shift all values one cell ahead

    for (int i = length; i > 0; i--) {

        a[i] = a[i-1];

    }

    // add new value as first cell 

    a[0] = x;

    length ++;

    }   

}