Arrays

新兵训练营

！！！插入和删除操作的代码必须非常熟悉

    /**
     * 数组插入元素
     * 插入和扩容操作的时间复杂度时O(N)
     *
     * @param element 待插入元素
     * @param index   位置索引
     */
    public void insert(int element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围");
        }
        //检查是否到达容量上限
        //扩容可使用System.arraycopy()方法（需要自行创建数组，但可以指定新数组及旧数组拷贝范围）
        //而Arrays.copyOf()方法，不用建立数组
        if (size >= array.length) resize();
        //从右向左循环，将元素挨个往右挪一位
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }

Tips:

• 如果插入元素是在数组尾部，传入元素下标index等于size，如果插入元素在数组中间或头部，则index小于size。

    /**
     * 删除操作的时间复杂度时O(N)
     *
     * @param index 待删除元素的索引
     * @return 删除元素
     */
    public int delete(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围");
        }
        int deletedElement = array[index];
        //从左向右循环，将元素挨个向左挪一位
        for (int i = index; i < size - 1; i--) {
            array[i] = array[i + 1];
        }
        size--;
        return deletedElement;
    }

Tips:

• 也不一定要背下来，那要背的东西数都数不过来了，但细节真的是魔鬼
• 我们就先考虑一般情况，比如说之前的插入操作，就在纸上写一个一般的数组，模拟在中间插入的情形，然后看现在的代码能不能处理尾部插入及头部插入又或是当前数组为空的情形，不行的话就打个补丁修正一下。