【漫画算法学习笔记】第二章——2.1数组

啵啵鱼

发布于 2022-11-23 18:03:49

2890

发布于 2022-11-23 18:03:49

文章被收录于专栏：Java一条龙学习笔记系列

文章目录

数组
- 1、数组算法之插入中间值

数组

1、数组算法之插入中间值

1.1、固定容量插中间值

编写工具类 ArrayUtil

package utils;

//数组算法之固定容量数组的中间值的插入
public class ArrayUtil {
    // private static int[] array;  //初始化一个数组
    private static int size = 0;  //数组实际存入的数据个数

/*
    //初始化ArrayUtil这个工具类 使用带参构造初始化 参数capacity为数组的容量
    public ArrayUtil(int capacity) {
        this.array = new int[capacity];
        size = 0; // size初始的个数为0
    }
*/


    /**
     * 数组固定容量插入中间值算法核心 插值
     *
     * @param index   元素插入的位置
     * @param element 插入的元素
     * @author BoBooY
     */
    public static void insert(int index, int element,int[] array) {
        //判断插入的数据下标是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }

        //从右想左循环遍历数组中的元素，将数组中 大于 插入元素的下标 的元素向右平移一个位置
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }

        //将元素插入到数组中
        array[index] = element;

        //数组实际存入的元素数量 + 1
        size++;
    }

    //输出数组
    public static void output(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

编写测试类 ArrayUtilTest

package utils;

public class ArrayUtilTest {
    public static void main(String[] args) {
        int[] array = new int[10];
        ArrayUtil.insert(0,1,array);
        ArrayUtil.insert(1,2,array);
        ArrayUtil.insert(2,4,array);
        ArrayUtil.insert(3,5,array);
        ArrayUtil.insert(4,6,array);
        ArrayUtil.insert(5,7,array);
        ArrayUtil.insert(6,8,array);

        ArrayUtil.insert(2,3,array); // 插入中间值
        ArrayUtil.output(array);
    }
}

插入中间值（2,3）前的数组输出结果

插入之后的结果

1.2、超容量插中间值

思路

超出数组的容量就给数组扩容

封装数组扩容方法

//数组扩容
public static int[] resize(int[] array) {
    int[] arrayNew = new int[array.length * 2];
    //System.arraycopy(原数组，从原数组的哪个位置copy，新数组，从新数组的哪个位置开始粘贴，粘贴原数组多少长度)
    System.arraycopy(array, 0, arrayNew, 0, array.length);
    array = arrayNew;  //将新数组赋值给旧数组的引用
    return array;
}

1.3、数组删除元素

//删除数组元素
public static int[] delete(int[] array, int index) {
    //判断插入的数据下标是否超出范围
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("超出数组实际元素范围！");
    }
    for (int i = index; i < size - 1; i++) {
        array[i] = array[i + 1];
    }
    size--;
    return array;
}

1.4、数组插值完整工具类

package utils;

import java.util.Arrays;

//数组算法之固定容量数组的中间值的插入
public class ArrayUtil {
    // private static int[] array;  //初始化一个数组
    private static int size = 0;  //数组实际存入的数据个数

/*
    //初始化ArrayUtil这个工具类 使用带参构造初始化 参数capacity为数组的容量
    public ArrayUtil(int capacity) {
        this.array = new int[capacity];
        size = 0; // size初始的个数为0
    }
*/


    /**
     * 数组固定容量插入中间值算法核心 插值
     *
     * @param index   元素插入的位置
     * @param element 插入的元素
     * @author BoBooY
     */
    public static int[] insert(int index, int element, int[] array) {

        //判断实际元素数量是否超出数组容量
        if (size >= array.length) {
            array = resize(array);
            System.out.println("对数组扩容了");
            System.out.println("插入前的数组：" + Arrays.toString(array) + "size:" + size);
        }

        //判断插入的数据下标是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }

        //从右想左循环遍历数组中的元素，将数组中 大于 插入元素的下标 的元素向右平移一个位置
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }

        //将元素插入到数组中
        array[index] = element;


        //数组实际存入的元素数量 + 1
        size++;
        System.out.println("插入后:" + Arrays.toString(array) + "size:" + size);
        return array;
    }

    //删除数组元素
    public static int[] delete(int[] array, int index) {
        //判断插入的数据下标是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return array;
    }

    //数组扩容
    public static int[] resize(int[] array) {
        int[] arrayNew = new int[array.length * 2];
        //System.arraycopy(原数组，从原数组的哪个位置copy，新数组，从新数组的哪个位置开始粘贴，粘贴原数组多少长度)
        System.arraycopy(array, 0, arrayNew, 0, array.length);
        array = arrayNew;  //将新数组赋值给旧数组的引用
        return array;
    }


    //输出数组
    public static void output(int[] array) {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

测试

package utils;

import java.util.Arrays;

public class ArrayUtilTest {
    public static void main(String[] args) {
        int[] array = new int[10];
        array = ArrayUtil.insert(0,1,array);
        array = ArrayUtil.insert(1,2,array);
        array = ArrayUtil.insert(2,4,array);
        array = ArrayUtil.insert(3,5,array);
        array = ArrayUtil.insert(4,6,array);
        array = ArrayUtil.insert(5,7,array);
        array = ArrayUtil.insert(6,8,array);
        array = ArrayUtil.insert(7,9,array);
        array = ArrayUtil.insert(8,10,array);
        array = array = ArrayUtil.insert(9, 11, array);
        array = array = ArrayUtil.insert(10,12,array);


        array = ArrayUtil.insert(2, 3, array);// 插入中间值

        System.out.println(Arrays.toString(array));
        ArrayUtil.output(array);
        System.out.println();

        //测试删除
        array = ArrayUtil.delete(array,2);
        System.out.println(Arrays.toString(array));
    }
}