数据结构之数组详解

桃扇骨 2022-03-07 09:06 286阅读 0赞

### 文章目录 ###

*  数组
 *   *  数组初始化的两种方法
     *  二次封装我们自己的数组
     *   *  添加方法
         *  重写toString方法
         *  数组中查询元素和修改元素
         *  数组中的包含、搜索和删除元素
     *  泛型数组
     *  动态数组
     *  数组的时间复杂度
     *  复杂度震荡

# 数组 #

数组的作用：把数据码成一排进行存放

## 数组初始化的两种方法 ##

*  指定容量

int[] arr = new int[20];

*  指定初始值

int[] scores = new int[]{100, 99, 66};

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

## 二次封装我们自己的数组 ##

/**
     * 二次封装我们自己的数组
     * Created by binzhang on 2019/3/15.
     */
    public class Array { 
        private int[] data;
        private int size;
    
        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){ 
            data = new int[capacity];
            size = 0;
        }
    
        // 无参数的构造函数，默认数组的容量capacity=10
        public Array(){ 
            this(10);
        }
    
        // 获取数组中的元素个数
        public int getSize(){ 
            return size;
        }
    
        // 获取数组的容量
        public int getCapacity(){ 
            return data.length;
        }
    
        // 返回数组是否为空
        public boolean isEmpty(){ 
            return size == 0;
        }
    
    }

### 添加方法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]  
size是数组的第一个空元素的定位符。

// 向所有元素后添加一个新元素
    public void addList(int e){ 
        if(size == data.length)
            throw new IllegalArgumentException("AddLast failed . Array is full.");
        data[size] = e;
        size ++;
    }

当遇到下面场景即向指定位置添加元素时要怎么办呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]  
首先将100后移一个位置，再依次将99，88后移一个位置，然后将77插入到索引为1的位置。

// 在第index个位置插入一个新元素e
    public void add(int index, int e){ 
        if(size == data.length)
            throw new IllegalArgumentException("AddLast failed . Array is full.");
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        for (int i = size -1; i>= index; i --)
            data[i + 1] = data[i];
    
        data[index] = e;
        size ++;
    }

这里其实可以在addLast里面复用我们的add方法了。

// 向所有元素后添加一个新元素
    public void addList(int e){ 
        add(size, e);
    }

在所有元素前添加一个新元素

// 在所有元素前添加一个新元素
    public void addFirst(int e){ 
        add(0,e);
    }

### 重写toString方法 ###

//重新toString方法输出数组信息
    @Override
    public String toString(){ 
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0 ; i < size ; i ++){ 
            res.append(data[i]);
            if(i != size-1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

验证toString方法和在指定位置插入元素方法输出：

public class Main { 
    
        public static void main(String[] args) { 
    
            Array arr = new Array(20);
            for (int i = 0 ; i < 10 ; i ++){ 
                arr.addLast(i);
            }
            System.out.println(arr);
        }
    }

输出：

Array: size = 10 , capacity = 20
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    Array: size = 11 , capacity = 20
    [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

### 数组中查询元素和修改元素 ###

// 获取index索引位置的元素
    public int get(int index){ 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Add failed. Index is illegal.");
        return data[index];
    }
    
    public E getLast(){ 
        return get(size - 1);
    }
    
    public E getFirst(){ 
        return get(0);
    }
        
    // 修改index索引位置的元素为e
    public void set(int index, int e){ 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Add failed. Index is illegal.");
        data[index] = e;
    }

### 数组中的包含、搜索和删除元素 ###

// 查找数组中是否有元素e
    public boolean contains(int e){ 
        for (int i = 0 ; i < size ; i ++){ 
            if (data[i] == e)
                return true;
        }
        return false;
    }
    
    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(int e){ 
        for (int i = 0 ; i < size ; i ++){ 
            if(data[i] == e)
                return i;
        }
        return -1;
    }

如下场景，想要删除索引为1的值为77的元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]  
将77后的元素都向左移一位即可，最后将size–

// 从数组中删除index位置的元素，返回删除的元素
    public int remove(int index){ 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Add failed. Index is illegal.");
        int res = data[index];
        for (int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null;
        return res;
    }

对应的可以写出相应的扩展方法

// 从数组中删除第一个元素，返回删除的元素
    public int removeFirst(){ 
        return remove(0);
    }
    
    // 从数组中删除最后一个元素，返回删除的元素
    public int removeLast(){ 
        return remove(size - 1);
    }
    
    // 从数组中删除元素e
    public void removeElement(int e){ 
        int index = find(e);
        if(index != -1)
            remove(index);
    }

## 泛型数组 ##

泛型数组

*  让我们的数据结构可以放置“任何”数据类型
 *  不可以是基本数据类型，只能是类对象
    
     *  boolean byte char short int long float double
 *  每个基本数据类型都有对应的包装类（可以使用）
    
     *  Boolean Byte Char Short Int Long Float Double

定义泛型数组：

/**
     * 定义泛型数组
     * Created by binzhang on 2019/3/15.
     */
    public class Array<E> { 
        private E[] data;
        private int size;
    
        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){ 
            data = (E[])new Object[capacity];
            size = 0;
        }
    	...
    }

声明泛型数组要传入要定义的类型  
`Array<Integer> arr = new Array<>(20);`

泛型数组使用示例：

/**
     * Created by binzhang on 2019/3/16.
     */
    public class Student { 
        private String name;
        private int score;
    
        public Student(String studentName, int studentScore){ 
            this.name = studentName;
            this.score = studentScore;
        }
    
        @Override
        public String toString() { 
            return String.format("Student(name: %s, score: %d)", name, score);
        }
    
        public static void main(String[] args) { 
            Array<Student> arr = new Array<>();
            arr.addLast(new Student("Alice", 100));
            arr.addLast(new Student("Bob", 99));
            arr.addLast(new Student("chili", 88));
            System.out.println(arr);
        }
    }

输出：

ArrayOld: size = 3 , capacity = 10
    [Student(name: Alice, score: 100), Student(name: Bob, score: 99), Student(name: chili, score: 88)]

## 动态数组 ##

动态数组可以简单理解为动态扩容，如下图所示当我们的data数组原容量只有4，且里面已经有四个元素，无法再次添加，我们可以先定义一个新数组newData，他的容量是data的二倍，将data中的数据拷贝到newData中，再将data指向newData，释放原数组的空间和newData引用，就完成了动态扩容，这就是动态数组。要注意的是，旧数组拷贝到新数组是要进行遍历的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 4]  
要实现上述过程，我们要改造之前写好了的add方法，加入的部分就是当要插入的位置size等于数组容量capacity/data.length时，进行动态扩容。

// 在第index个位置插入一个新元素e
    public void add(int index, E e){ 
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    
        if(size == data.length)
            resize(2 * data.length);
    
        for (int i = size -1; i>= index; i --)
            data[i + 1] = data[i];
    
        data[index] = e;
        size ++;
    }
    
    // 扩容方法设置为私有的，用户不可在外部调用
    private void resize(int newCapacity){ 
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }

这样我们就再也不用担心数组空间不够用了。  
同理我们也可以考虑在remove方法中加入动态减少数组空间的操作了。

// 从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){ 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Add failed. Index is illegal.");
    
        E res = data[index];
        for (int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null;
    
        // 动态减少数组容量
        if (size == data.length / 2 && data.length / 2 != 0)
            resize(data.length / 2);
    
        return res;
    }

## 数组的时间复杂度 ##

*  O(1)，O(n)，O(nlogn)，O(n^2)
 *  大O描述的是算法的运行时间和输入数据之间的关系

分析动态数组的时间复杂度

*  添加操作 O(n)
    
     *  addLast(e) O(1)
     *  addFirst(e) O(n)
     *  add(index, e) O(n/2) = O(n)

> 时间复杂度我们通常考虑最糟糕的情况，所以添加操作的时间复杂度就是O(n)

*  删除操作 O(n)
    
     *  removeLast(e) O(1)
     *  removeFirst(e) O(n)
     *  remove(index, e) O(n/2) = O(n)
 *  修改操作
    
     *  set(index, e) O(1)
 *  查找操作 O(n)
    
     *  get(index) O(1)
     *  contains(e) O(n)
     *  find(e) O(n)

总结：

*  增：O(n)
 *  删：O(n)
 *  改：已知索引O(1)；未知索引O(n)
 *  查：已知索引O(1)；未知索引O(n)

> 注意对于增删最后一条元素，因为要考虑到resize所以时间复杂度依然是O(n)

## 复杂度震荡 ##

**复杂度震荡问题**：当我们的数组容量满的时候，再次添加一个元素，会触发扩容机制，然后再将这个元素删除，又会触发缩减容量的机制，明显这样对我们系统的资源是很大的浪费。

**出现问题的原因**：removeLast时resize过于着急（Eager）

**解决方法**：当 size == capacity / 4 时，才将capacity减半（Lazy）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220307/664d9b1f061b4885b047aff73f6e5766.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220307/c07ff701d7844ecd8e2ca051a7fcdffb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]: /images/20220307/3cb5f74aa9644e41ab5856fac9793262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]: /images/20220307/05e2dd4bf3f546cfaf5aac5d83b076e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 4]: /images/20220307/7d36324854dd448aab325218df0e977e.png