Array|数组

定义

  • 把数据码成一排进行存放
  • In Java, all data must be of the same type
  • In Python, we can store different data types
  • Index, usually start from 0 (R starts from 1)
  • 数组支持for, forEach因为它具有可迭代,可遍历的能力 (iterable)

二次封装属于我们自己的数组

数组最大的优点:快速查询

索引最好有语义

并非所有有语义的索引都适用于数组

比如ID号,开辟的空间大,可能会浪费

制作属于我们自己的数组类

索引没有语义,如何表示没有元素?

如何添加元素?如何删除元素?

增删改查

向指定位置添加元素

  • 确定数组中有足够的空间:size < capacity

  • 确定插入的位置合法:index >= 0 并且 index <= capacity

Dynamic Array Code

用Java实现动态数组

public class DynaArray {
  private int[] data;
  private int size;

  // 构造函数, 传入数组的容量capacity构造DynaArray
  public DynaArray(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  // 无参数的构造函数,默认容量capacity为10
  public DynaArray() {
    this(10);
  }

  // 获取数组中的元素个数
  public int getSize() {
    return size;
  }

  // 获取数组的容量
  public int getCapacity() {
    return data.length;
  }

  // 查询数组是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  // 向数组末尾添加元素
  public void addLast(int e) {
    add(size, e);
  }

  // 向数组头部添加元素
  public void addFirst(int e) {
    add(0, 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("addLast Failed, require index >= 0 and index <= size");
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
  }

  // 获取index索引位置的元素
  int get(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    return data[index];
  }

  // 更新index索引位置的元素
  void set(int index, int e) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    data[index] = e;
  }
  // 查找数组中是否有元素e
  public boolean contains(int e) {
    for (int d : data) {
      if (d == e) {
        return true;
      }
    }
    return false;
  }
  // 查找包含元素的索引,如果不存在,返回-1
  public int find(int e) {
    for (int i = 0; i < size; i++) {
      if (data[i]==e) {
        return i;
      }
    }
    return -1;
  }

  // 删除索引位置的元素,返回删除的元素
  public int remove(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    int deleted = data[index];

    for (int i = index + 1; i < size; i++) {
      data[i - 1] = data[i];
    }
    size--;
    return deleted;
  }

  // 快捷删除第一个
  public int removeFirst() {
    return remove(0);
  }

  // 快捷删除最后一个
  public int removeLast() {
    return remove(size - 1);
  }

  // 删除元素e
  public void removeElement(int e) {
    int idx = find(e);
    if (idx != -1) {
      remove(idx);
    }
  }

  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("Dynamic Array: size=%d, capacity=%d\n", size, data.length));
    res.append("[");
    for (int i = 0; i < size; i++) {
      // res.append(String.format("%d", data[i]));
      res.append(data[i]);
      if (i != size - 1) {
        res.append(", ");
      }
    }
    res.append("]");

    return res.toString();
  }

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

    arr.add(1, 100);
    System.out.println(arr);

    arr.addFirst(-5);
    System.out.println(arr);

    arr.remove(2);
    System.out.println(arr);

    arr.removeFirst();
    System.out.println(arr);

    arr.removeElement(4);
    System.out.println(arr);
  }
}
 Dynamic Array: size=10, capacity=20
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 Dynamic Array: size=11, capacity=20
 [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 Dynamic Array: size=12, capacity=20
 [-5, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 Dynamic Array: size=11, capacity=20
 [-5, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 Dynamic Array: size=10, capacity=20
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 Dynamic Array: size=9, capacity=20
 [0, 1, 2, 3, 5, 6, 7, 8, 9]

使用泛型

让我们的数据结构可以放置“任何”数据类型

不可以是基本数据类型,只能是类对象

  • 8种基本数据类型

    boolean, byte, char, short, int, long, float, double

  • 每个基本数据类型都有对应的包装类

    Boolean, Byte, Char, Short, Int, Long, Float, Double

Autoboxing 基本类型自动转化为包装类

General Dynamic Array Code

// add <E> 声明泛型
public class GenArray<E> {
  private E[] data;
  private int size;

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

  // 无参数的构造函数,默认容量capacity为10
  public GenArray() {
    this(10);
  }

  // 获取数组中的元素个数
  public int getSize() {
    return size;
  }

  // 获取数组的容量
  public int getCapacity() {
    return data.length;
  }

  // 查询数组是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  // 向数组末尾添加元素
  public void addLast(E e) {
    add(size, e);
  }

  // 向数组头部添加元素
  public void addFirst(E e) {
    add(0, e);
  }

  // 向指定位置添加元素
  public void add(int index, E e) {
    if (size >= data.length) {
      throw new IllegalArgumentException("addLast Failed, Array is full");
    }
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
  }

  // 获取index索引位置的元素
  public E get(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    return data[index];
  }

  // 更新index索引位置的元素
  public void set(int index, E e) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    data[index] = e;
  }
  // 查找数组中是否有元素e
  public boolean contains(E e) {
    for (E d : data) {
      if (d.equals(e)) {
        return true;
      }
    }
    return false;
  }
  // 查找包含元素的索引,如果不存在,返回-1
  public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e)) {
        return i;
      }
    }
    return -1;
  }

  // 删除索引位置的元素,返回删除的元素
  public E remove(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    E deleted = data[index];

    for (int i = index + 1; i < size; i++) {
      data[i - 1] = data[i];
    }
    size--;
    data[size] = null;          // loitering objects != memory leak, not necessary
    return deleted;
  }

  // 快捷删除第一个
  public E removeFirst() {
    return remove(0);
  }

  // 快捷删除最后一个
  public E removeLast() {
    return remove(size - 1);
  }

  // 删除元素e
  public void removeElement(E e) {
    int idx = find(e);
    if (idx != -1) {
      remove(idx);
    }
  }

  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("General Dynamic Array: size=%d, capacity=%d\n", size, data.length));
    res.append("[");
    for (int i = 0; i < size; i++) {
      // res.append(String.format("%d", data[i]));
      res.append(data[i]);
      if (i != size - 1) {
        res.append(", ");
      }
    }
    res.append("]");

    return res.toString();
  }

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

    arr.add(1, 100);
    System.out.println(arr);

    arr.addFirst(-5);
    System.out.println(arr);

    arr.remove(2);
    System.out.println(arr);

    arr.removeFirst();
    System.out.println(arr);

    arr.removeElement(4);
    System.out.println(arr);
  }
}
General Dynamic Array: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=12, capacity=20
[-5, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[-5, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=9, capacity=20
[0, 1, 2, 3, 5, 6, 7, 8, 9]

自定义类型

Customize Class Code

public class Student{
    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString(){
        return String.format("Student(name: %s, score: %d)", name, score);
    }

    public static void main(String[] args) {
        GenArray<Student> arr = new GenArray<>();
        arr.addLast(new Student("Isaac", 100));
        arr.addLast(new Student("Alice", 66));
        arr.addLast(new Student("Charlie", 88));
        System.out.println(arr);
    }

}
General Dynamic Array: size=3, capacity=10
[Student(name: Isaac, score: 100), Student(name: Alice, score: 66), Student(name: Charlie, score: 88)]

动态数组

  • 现在的数组还是静态的
  • 扩容:把数组变成可伸缩的,开辟一个新的空间,赋值到新的空间
  • 减容:同理,当数组的元素被删除到一定程度,减少数组的空间

Dynamic Array

// add <E> 声明泛型
public class DGArray<E> {
  private E[] data;
  private int size;

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

  // 无参数的构造函数,默认容量capacity为10
  public DGArray() {
    this(10);
  }

  // 获取数组中的元素个数
  public int getSize() {
    return size;
  }

  // 获取数组的容量
  public int getCapacity() {
    return data.length;
  }

  // 查询数组是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  // 向数组末尾添加元素
  public void addLast(E e) {
    add(size, e);
  }

  // 向数组头部添加元素
  public void addFirst(E e) {
    add(0, e);
  }

  // 向指定位置添加元素
  public void add(int index, E e) {

    if (index < 0 || index > size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    if (size >= data.length) {
        // 如果数组满了,进行扩容, *2 扩容的量和当前的量有关
        resize(2*data.length);
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
  }

  // 获取index索引位置的元素
  public E get(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    return data[index];
  }

  // 更新index索引位置的元素
  public void set(int index, E e) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    data[index] = e;
  }
  // 查找数组中是否有元素e
  public boolean contains(E e) {
    for (E d : data) {
      if (d.equals(e)) {
        return true;
      }
    }
    return false;
  }
  // 查找包含元素的索引,如果不存在,返回-1
  public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e)) {
        return i;
      }
    }
    return -1;
  }

  // 删除索引位置的元素,返回删除的元素
  public E remove(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    E deleted = data[index];

    for (int i = index + 1; i < size; i++) {
      data[i - 1] = data[i];
    }
    size--;
    data[size] = null;          // loitering objects != memory leak, not necessary
    if (size==data.length/2) {
        resize(data.length/2);
        }
    return deleted;
  }

  // 快捷删除第一个
  public E removeFirst() {
    return remove(0);
  }

  // 快捷删除最后一个
  public E removeLast() {
    return remove(size - 1);
  }

  // 删除元素e
  public void removeElement(E e) {
    int idx = find(e);
    if (idx != -1) {
      remove(idx);
    }
  }

  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("General Dynamic Array: size=%d, capacity=%d\n", size, data.length));
    res.append("[");
    for (int i = 0; i < size; i++) {
      // res.append(String.format("%d", data[i]));
      res.append(data[i]);
      if (i != size - 1) {
        res.append(", ");
      }
    }
    res.append("]");

    return res.toString();
  }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

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

    // 扩容
    arr.add(1, 100);
    System.out.println(arr);
    arr.addFirst(-5);
    System.out.println(arr);

    arr.remove(2);
    System.out.println(arr);
    arr.removeElement(-5);
    System.out.println(arr);
    // 减容
    arr.removeFirst();
    System.out.println(arr);
  }
}
General Dynamic Array: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=12, capacity=20
[-5, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[-5, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=9, capacity=10
[1, 2, 3, 4, 5, 6, 7, 8, 9]

复杂度分析

Big O

  • 大O描述的是算法的运行时间和输入数据之间的关系
  • O(n) 算法和n呈线性关系
  • 渐进时间复杂度,描述n趋近于无穷的情况
  • 低阶项会被忽略掉

Array方法的例子

  • 添加操作

    • 综合起来是O(n),考虑最坏的情况
    • addLast(e): O(1), 数组最后添加元素和数组大小无关
    • addFirst(e): O(n), 第一个元素添加完后,其后面的每一个元素要后移
    • add(index, e): 跟index位置有关,index=0,O(n); index=size, O(1);平均下来O(n/2)=O(n)
    • resize: O(n)
  • 删除操作

    • 综合起来O(n)
    • removeLast(e): O(1)
    • removeFirst(e): O(n)
    • remove(index, e): O(n)
    • resize: O(n)
  • 修改操作

    • set(index, e): O(1), 只要知道修改元素的索引,和数组大小无关, a.k.a支持随机操作
  • 查找操作

    • 综合起来O(n)
    • get(index): O(1)
    • contains(e): O(n)
    • find(e): O(n)
  • 增删改查

    • 增: O(n)

    • 删: O(n)

    • 改: O(1) 已知索引;O(n) 未知索引

    • 查: O(n)

均摊复杂度

addLast

  • 假设当前capacity=8,并且每一次添加操作都使用addLast
  • 到第9次时:已经添加了8次,扩容O(n)=8,再添加一次=8+8+1=17次
  • 假设capacity=n, 到第n+1次时触发resize,复杂度是2n+1次
  • 在这个例子里,因为最坏情况出现的频率极低,随着n增加也会越来越小。这样均摊计算,比计算最坏情况有意义。
  • 均摊复杂度amortized time complexity = O(1)
  • 同理removeLast均摊复杂度也是O(1)

防止复杂度震荡

addLast和removeLast特例

  • capacity=n, 当size=n, addLast将触发扩容,复杂度O(n)
  • 紧接着,removeLast将触发减容,复杂度O(n)
  • 循环下去,这个特例的复杂度将会是O(n)
  • 这就产生了复杂度的震荡

原因

  • 出现问题的原因:removeLast时resize的过于着急 (too Eager)
  • 解决方案:Lazy,当size==capacity/4,才将capacity减半

Lazy Resize Code

// add <E> 声明泛型
public class LazyArr<E> {
  private E[] data;
  private int size;

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

  // 无参数的构造函数,默认容量capacity为10
  public LazyArr() {
    this(10);
  }

  // 获取数组中的元素个数
  public int getSize() {
    return size;
  }

  // 获取数组的容量
  public int getCapacity() {
    return data.length;
  }

  // 查询数组是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  // 向数组末尾添加元素
  public void addLast(E e) {
    add(size, e);
  }

  // 向数组头部添加元素
  public void addFirst(E e) {
    add(0, e);
  }

  // 向指定位置添加元素
  public void add(int index, E e) {

    if (index < 0 || index > size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    if (size >= data.length) {
        // 如果数组满了,进行扩容, *2 扩容的量和当前的量有关
        resize(2*data.length);
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
  }

  // 获取index索引位置的元素
  public E get(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    return data[index];
  }

  // 更新index索引位置的元素
  public void set(int index, E e) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    data[index] = e;
  }
  // 查找数组中是否有元素e
  public boolean contains(E e) {
    for (E d : data) {
      if (d.equals(e)) {
        return true;
      }
    }
    return false;
  }
  // 查找包含元素的索引,如果不存在,返回-1
  public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e)) {
        return i;
      }
    }
    return -1;
  }

  // 删除索引位置的元素,返回删除的元素
  public E remove(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("addLast Failed, require index >= 0 and index <= size");
    }
    E deleted = data[index];

    for (int i = index + 1; i < size; i++) {
      data[i - 1] = data[i];
    }
    size--;
    data[size] = null;          // loitering objects != memory leak, not necessary
    if (size==data.length/4 && data.length/2 != 0){
        //lazy resize, 并且加入data.length = 1后 data.length/2 会等于0的情况
        resize(data.length/2); //lazy resize, 依然减容成data.length/2
        }
    return deleted;
  }

  // 快捷删除第一个
  public E removeFirst() {
    return remove(0);
  }

  // 快捷删除最后一个
  public E removeLast() {
    return remove(size - 1);
  }

  // 删除元素e
  public void removeElement(E e) {
    int idx = find(e);
    if (idx != -1) {
      remove(idx);
    }
  }

  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("General Dynamic Array: size=%d, capacity=%d\n", size, data.length));
    res.append("[");
    for (int i = 0; i < size; i++) {
      // res.append(String.format("%d", data[i]));
      res.append(data[i]);
      if (i != size - 1) {
        res.append(", ");
      }
    }
    res.append("]");

    return res.toString();
  }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

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

    // 扩容
    arr.add(1, 100);
    System.out.println(arr);
    arr.addFirst(-5);
    System.out.println(arr);

    arr.remove(2);
    System.out.println(arr);
    arr.removeElement(-5);
    System.out.println(arr);
    arr.removeFirst();
    System.out.println(arr);
    arr.removeFirst();
    arr.removeFirst();
    arr.removeFirst();
    System.out.println(arr);
    //触发减容
    arr.removeFirst();
    System.out.println(arr);
  }
}
General Dynamic Array: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=12, capacity=20
[-5, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=11, capacity=20
[-5, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=9, capacity=20
[1, 2, 3, 4, 5, 6, 7, 8, 9]
General Dynamic Array: size=6, capacity=20
[4, 5, 6, 7, 8, 9]
General Dynamic Array: size=5, capacity=10
[5, 6, 7, 8, 9]