数据结构数组

数组这种数据结构想必小伙伴们看到它定会 低头，想象一秒钟，嘴角一翘：“啊，是他”

• 数组想必大家都很熟悉，熟悉java的小伙伴可能瞬间就想到了Array，但是有没有想到它的细节之处呢。
• 本文从数组是什么到数组的各个操作的时间复杂度来详细分析数组的特性
• 想必是老司机或者是新手都会有所收获

什么是数组

• 把数据码成一排进行存放，类似麻将。大家可以想象一下码好的整齐排列的麻将
• 我们常说的第几个麻将 这个数字就是它的索引 每个麻将是什么就是它的值

• 数组最大的优点是快速的查找，例如查找索引是5的元素，也即支持随机查找
• 数组的容量在初始化的时候就固定了下来。那么问题来了 如果往一个容量满的数组中添加元素会发生什么呢？怎么解决呢，如果删除和新增元素呢
• 下面我们写一个我们自定义的数组类

自定义数组类

• 自定义一个MyArray类
• 其中包含 增、删、改、查 的基础方法，初体验数组的魅力

public class MyArray {

    private E[] data;
    private int size;

    // 构造函数，传入数组容量
    public MyArray(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 增
    //在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index  size){
            throw new IllegalArgumentException("索引非法");
        }
        
        if(size == data.length){
            throw new IllegalArgumentException("数组已满");
        }
        
        //依次将元素向后移动一位，并在index处设置新元素
        for(int i = size - 1; i >= index ; i --){
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }
    
    //删
    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index = size){
            throw new IllegalArgumentException("索引非法");
        }
        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++){
            data[i - 1] = data[i];
        }
        size --;
        data[size] = null;
        
        return ret;
    }
    
    //改
    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index = size){
            throw new IllegalArgumentException("索引非法");
        }
        data[index] = e;
    }

    //查
    // 获取index索引位置的元素
    public E get(int index){
        if(index = size){
            throw new IllegalArgumentException("索引非法");
        }
        return data[index];
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %dn", 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();
    }
}

• 到此我们自定义的数组类就实现好了，可以看到其中包含基础的方法，并且支持泛型
• 但是我们观察add方法，如果数组满了就会抛出异常，显然不是很丝滑，那么新需求来了，要支持自动扩容，也即动态数组
• 那么接着上述问题remove方法，删除完毕之后要支持自动缩容。那么我们修改上面的代码，加上自动扩容的逻辑。
• 如果添加元素的时候数组已经满了，那么将数组扩容到原来大小的二倍，并将原有的元素放到新数组中返回。
• 如果删除元素的时候，发现元素个数是数组容量的一半，就将容量缩到一半。

//添加扩容的代码
//新建一个空数组，并将原来数组中的元素依次放到新数组中 返回
private void resize(int newCapacity){
    E[] newData = (E[])new Object[newCapacity];
    for(int i = 0 ; i < size ; i ++){
        newData[i] = data[i];
    }
    data = newData;
}

//在添加元素的方法中调用上面的resize方法
public void add(int index, E e){
    if(index  size){
        throw new IllegalArgumentException("索引非法");
    }
    //如果添加元素的时候数组已经满了，那么将数组扩容到原来大小的二倍
    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 ++;
}

//在删除元素的方法中调用上面的resize方法
public E remove(int index){
    if(index  size){
        throw new IllegalArgumentException("索引非法");
    }
    E ret = data[index];
    for(int i = index + 1 ; i < size ; i ++){
        data[i - 1] = data[i];
    }
    size --;
    data[size] = null; // 释放无用的引用

    //如果删除元素之后的元素个数是数组容量的一半，就将容量缩小
    if(size == data.length / 2){
        resize(data.length / 2);
    }
    return ret;
}

• 到此一个动态的数组就构建好了，也可以实现简单的添加和删除元素等操作，不知道小伙伴有没有疑问，数组的各种操作的时间复杂度是多少？ 以及为什么会是这样？
• 带着这个疑问，开始解答

时间复杂度

基础操作

• 添加操作：O(n)
  • 这个时间复杂度想必有些疑惑，因为如果我们在末尾添加一个元素的时候仅仅需要在末尾那个索引上设置值就好了 应该是O(1)才对，那么我们详细分析一下。
  • 如果在头添加一个元素会发生什么呢，我们观察add方法，会将后面所有的元素依次往后移动一位，有多少个元素就会移动多少次，显然这个操作的时间复杂度是O(n)
  • 如果在末尾添加一个元素，没有疑问是O(1)
  • 排除上面两种极端情况，在元素中进行添加操作移动元素的次数是多少次呢？在概率学上讲多次重复实验平均下来应该是n/2次（小伙伴们多想几次就会相通，在数组的前面添加移动的就会多，在后面添加移动的就会少，平均下来就是一半的量）那么时间复杂度会是O(n/2) 吗，其实实际的算法结果是O(n) 的
  • 我们在计算时间复杂度的时候会根据最坏的情况来分析，也即添加操作的时间复杂度是O(n)的
• 删除操作：O(n)
  • 有了上面添加操作的分析过程，想必删除操作也是和添加操作类似
  • 删除头元素：由于删除完之后需要向前移动一位所以是O(n)
  • 删除末尾元素：O(1)
  • 排除上面两种极端情况：O(n)
• 修改操作：O(1)
• 查询操作: O(n)
  • 这里又会有些疑惑，根据索引get元素的时间复杂度不是O(1)嘛，怎么会是O(n)呢？
  • 小伙伴想一想 如果我想根据元素的值去获取呢，是不是要循环整个数组元素，找到我要找的值返回，所以这里是O(n)

复杂度均摊与震荡

• 复杂度均摊

  • 不知道小伙伴们有没有发现这样的事情，上面我们说时间复杂度是根据最坏的情况考虑的，所以添加操作的时间复杂度是O(n)。但是如果在元素末尾添加时间复杂度显然是O(1)的，这样会不会不公平呢？
  • 所以我们提出来均摊复杂度。们重新完整的分析在末尾添加元素的操作，不要忘记，还有resize操作
  • 假设当前capacity=5,每次在末尾添加元素，那么6次的添加就会触发resize操作，就会进行11次操作(因为第6次添加的时候触发扩容，会把原来的5个元素添加进新元素中，所以5+6=11)，平均每次在末尾添加元素会进行两次基本操作，这样均摊之后，时间复杂度是O(1)的
  • 这样的例子中使用均摊计算，比只考虑最坏的情况有意义

• 复杂度震荡

  • 我们回忆下上面的添加和删除中的扩容与缩容操作，考虑一下这个场景：
  • 当前数组是满的，这个时候执行添加操作，会扩容
  • 紧接着删除了一个元素，触发缩容条件，进行缩容
  • 紧接着又添加了一个元素，触发扩容....无限循环
  • 这种反复的频繁在临界点操作，会造成复杂度的震荡
  • 出现这种问题的原因是因为我们在触发resize的时候太过激进了，试想一下，如果我们在删除元素之后，不立即缩容，也即原来是size达到capacity的一半就会缩容，缩容之后数组也是满的，修改成size达到capacity 1/4 的时候在缩容，缩容还是缩capacity的一半，会不会好很多呢，缩容之后的数组也不是满的，还是可以继续添加元素，不会触发resize。

到此 数组这个数据结构就介绍完了，大家有没有感受到数组的特点呢