Arrays

当你需要保存一系列元素，又需要用序号来访问——使用数组【查询：运行复杂度O(1)】

局限性：长度是固定的【插入：复制原数组到新数组时，此时运行复杂度为O(n)，也就是说，这个操作的时间消耗，与源数组的大小成线性正比关系】；若需要删除也是需要【O(n)：复杂度只考虑最坏的情况】——这时候就需要换用List

注释：我们只有在解释为何和如何的时候才需要注释

Lookup：O(1)
Insert：O(n)
Delete：O(n)

        int[] numbers = new int[3]; //也可大括号进行初始化
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        System.out.println(numbers.length);
        //toString：这个方法会将数组转为字符串，然后再输出到控制台
        System.out.println(Arrays.toString(numbers));

可变数组练习

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Array numbers = new Array(3);
        numbers.insert(10);
        numbers.insert(20);
        numbers.insert(30);
        numbers.removeAt(3);
        numbers.printf();   //[10 20 30]
        System.out.println(numbers.indexOf(80));    //-1
    }
}

class Array {
    int[] numbers;
    int i = 0;//判断数组长度
    //传入数组长度
    public Array(int length) {
        numbers = new int[length];
    }

    //插入
    public void insert(int item) {
        if (i < numbers.length) {
            numbers[i] = item;
            i++;
        } else {
            //临时数组
            int[] numbers1 = new int[numbers.length];
            for (int j = 0; j < numbers.length; j++) {
                numbers1[j] = numbers[j];
            }
            //创建新数组——增大数组长度
            numbers = new int[numbers.length + 1];
            for (int j = 0; j < numbers.length - 1; j++) {
                numbers[j] = numbers1[j];
            }
            numbers[numbers.length - 1] = item;
            i++;//判断更改数组长度
        }
    }

    public void removeAt(int index) {
        int[] numbers1;
        int k = 0;//新数组角标变量
        if (index < numbers.length) {
            //临时数组
            numbers1 = new int[numbers.length - 1];
            for (int j = 0; j < numbers.length; j++) {
                if (index == j) {
                   //相同的不用操作，则可得到删除作用
                } else {
                    numbers1[k] = numbers[j];
                    k++;
                }
            }
            //创建新数组——减小数组长度
            numbers = new int[numbers.length - 1];
            for (int j = 0; j < numbers.length; j++) {
                numbers[j] = numbers1[j];
            }
            i--;//判断更改数组长度
        } else {
            System.out.println("没有");
        }
    }

    public int indexOf(int a) {
        //寻找角标
        for (int j = 0; j < numbers.length; j++) {
            if (a == numbers[j]) {
                return j;
            }
        }
        //没有则返回-1
        return -1;
    }

    //遍历
    public void printf() {
        System.out.print("[");
        for (int j = 0; j < i; j++) {
            System.out.print(numbers[j] + " ");
        }
        System.out.print(numbers[numbers.length - 1]);
        System.out.println("]");
    }
}

讲解：

第一步：创建类

public class Main {
    public static void main(String[] args) {
        Array numbers = new Array(3);
        numbers.print();
    }
}
public class Array {
    //私有
    private int[] items;
    private int count;
    public Array(int length) {
        //初始化数组
        items = new int[length];
    }
    public void print() {
//应该考虑分配的内容有多少，可能分配50个，实际上只插入两个——>创建一个count变量计数
        //没有插入时循环不会开始，插入时count++;
        for (int i = 0; i < count; i++) {
            System.out.println(items[i]);
        }
    }
}

insert方法

public void insert(int item) {
        //如果数组满了，重新设定大小(If the array is full, resize it)
        if (items.length == count) {
            //创建一个新的数组(2倍)
            int[] newItems = new int[count * 2];
            //复制所有存在的元素
            for (int i = 0; i < count; i++) {
                newItems[i] = items[i];
            }
            // Set "items" to this new array
            items = newItems;
        }
        //Add the new Item at the end
        items[count++] = item;
    }

removeAt方法

public void removeAt(int index) {
        //验证index
        if (index < 0 || index >= count){
            throw new IllegalArgumentException();
        }
        //删除后向前填补位置
        for (int i=index;i<count;i++)
            items[i] = items[i+1];
        count--;
    }

indexOf方法

public int indexOf(int item){
        //If we find it, return index
        //Otherwise, return -1
        for (int i = 0; i < count; i++) {   //O(n)
            if (items[i] == item)
                return i;
        }
        return -1;
    }

Array类

package cn.arithmetic02;

public class Array {
    private int[] items;
    private int count;  //当前数组内实际元素
    public Array(int length) {
        items = new int[length];
    }
    public void insert(int item) {
        if (items.length == count) {
            int[] newItems = new int[count * 2];
            for (int i = 0; i < count; i++) {
                newItems[i] = items[i];
            }
            items = newItems;
        }
        items[count++] = item;
    }
    public void removeAt(int index) {
        if (index < 0 || index >= count)
            throw new IllegalArgumentException();
        for (int i=index;i<count;i++)
            items[i] = items[i+1];
        count--;
    }
    public int indexOf(int item){
        //O(n)
        for (int i = 0; i < count; i++) {   
            if (items[i] == item)
                return i;
        }
        return -1;
    }
    public void print() {
        for (int i = 0; i < count; i++) 
            System.out.println(items[i]);
    }
}

动态数组（Vector和ArrayList）

Vector：100%（满时的扩展）—— 同步

ArrayList：50% —— 异步

同步方法可以理解为，只有一个线程可以访问这个方法；如果我们的程序是多线程的，也就是，多线程可以操作这些集合，这些线程就无法用于Vector类，你就需要使用ArrayList类，因为这个类的方法是异步的

import java.util.ArrayList;

public class Array02 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(10);
        list.add(20);
        list.add(30);
        list.remove(0);
        list.indexOf(20);   //0
        list.lastIndexOf(30);  //会返回给定项最后出现的位置
        list.contains(20);  //true or false
        list.size();
        list.toArray(); //转化为数组
        System.out.println(list);
    }
}

image.png