數據結構篇-數組（TypeScript版+Java版）

• 2020 年 4 月 16 日
• 筆記
• 【*****演算法*****】

1.TypeScript版本

export default class MyArray<E> {

  public data: E[];
  public size: number = 0;

  /**
   * 構造函數，傳入數組的容量capacity
   * @param {number} capacity 數組容量，默認10
   */
  constructor(capacity = 10) {
    this.data = new Array(capacity);
  }

  /**
   * 獲取數組容量（數組能總共能包含多少元素）
   * Time Complexity O(1)
   * @return {number}
   */
  getCapacity(): number {
    return this.data.length;
  }

  /**
   * 獲取數組中當前存儲元素的個數
   * Time Complexity O(1)
   * @return {number}
   */
  getSize(): number {
    return this.size;
  }

  /**
   * 判斷數組是否為空，即元素的個數是否為0
   * Time Complexity O(1)
   * @return {boolean}
   */
  isEmpty(): boolean {
    return this.size === 0;
  }

  /**
   * 在數組中index位置添加一個元素
   * 考慮到這裡不是每次操作都會觸發擴容，這裡均攤到每次操作上的時間複雜度為O(1)
   * @param {number} index 要插入的位置
   * @param {E} e 要插入的元素
   * @return {void}
   */
  add(index: number, e: E): void {
    if (index < 0 || index > this.size) {
      throw new Error('Add failed. Required index >= 0 and index <= size');
    }

    // 將數組的容量擴大為之前的二倍
    if (this.size === this.data.length) {
      this.resize(this.data.length * 2);
    }
    for (let i = this.size - 1; i >= index; i--) {
      this.data[i + 1] = this.data[i];
    }
    this.data[index] = e;
    this.size++;
  }

  /**
   * 向所有元素之後添加一個元素
   * Time Complexity O(1)
   * @param {E} e 要插入的元素
   * @return {void}
   */
  addLast(e: E): void {
    this.add(this.size, e);
  }

  /**
   * 向所有元素之前添加一個元素
   * Time Complexity O(n)
   * @param {E} e 要插入的元素
   * @return {void}
   */
  addFirst(e: E): void {
    this.add(0, e);
  }

  /**
   * 修改index索引位置元素為e
   * Time Complexity O(1)
   * @param {number} index 要插入元素的位置
   * @param {E} e 要插入的元素
   * @return {void}
   */
  set(index: number, e: E) {
    if (index < 0 || index >= this.size) {
      throw new Error('Set failed. Index is illegal.');
    }
    this.data[index] = e;
  }

  /**
   * 查找數組中是否含有元素e
   * Time Complexity O(n)
   * @param {E} e 要查找的元素
   * @return {boolean}
   */
  contains(e: E): boolean {
    for (let i = 0; i < this.size; i++) {
      if (e === this.data[i]) {
        return true;
      }
    }
    return false;
  }

  /**
   * 查找數組中元素e所在的索引，如果不存在，則返回-1
   * Time Complexity O(n)
   * @param {E} e 要查找的元素
   * @return {boolean}
   */
  find(e: E): number {
    for (let i = 0; i < this.size; i++) {
      if (e === this.data[i]) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 從數組中刪除index位置的元素，並且返回刪除元素
   * Time Complexity O(n)
   * @param {number} index 要刪除的元素位置的索引
   * @return {E}
   */
  remove(index: number): E {
    if (index < 0 || index > this.size) {
      throw new Error('Remove failed. index is illegal')
    }

    let ret: E = this.data[index];
    for (let i = index + 1; i < this.size; i++) {
      this.data[i - 1] = this.data[i];
    }
    this.size--;
    this.data[this.size] = null;
    // 當size == capacity / 4時，才將capacity減半。防止複雜度震蕩
    // data.length != 0 是因為不能常見capacity為0的數組
    if (this.size === Math.floor(this.data.length / 4) && Math.floor(this.data.length / 2) !== 0) {
      this.resize(Math.floor(this.data.length / 2));
    }
    return ret;
  }

  /**
   * 刪除數組中的最後一個元素
   * Time Complexity O(1)
   * @return {E}
   */
  removeLast(): E {
    return this.remove(this.size - 1);
  }

  /**
   * 刪除數組中的第一個元素
   * Time Complexity O(n)
   * @return {E}
   */
  removeFirst(): E {
    return this.remove(0);
  }

  /**
   * 獲取index索引的元素
   * Time Complexity O(1)
   * @param {number} index 要獲取元素的索引
   * @return {E}
   */
  get(index: number): E {
    if (index < 0 || index >= this.size) {
      throw new Error('Get failed. Index is illegal...')
    }
    return this.data[index];
  }

  /**
   * 獲取數組中的第一個元素
   * Time Complexity O(1)
   * @return {E}
   */
  getFirst() {
    return this.get(0);
  }

  /**
   * 獲取數組中的最後一個元素
   * Time Complexity O(1)
   * @return {E}
   */
  getLast() {
    return this.get(this.size - 1);
  }

  /**
   * 數組擴容，或者縮容操作
   * Time Complexity O(n)
   * @param {number} newCapacity 新的數組的容量
   * @return {void}
   */
  resize(newCapacity: number): void {
    let newData: E[] = new Array(newCapacity);
    for (let i = 0; i < this.size; i++) {
      newData[i] = this.data[i];
    }

    this.data = newData;
  }

  /**
   * 交換數組中的i, j兩個元素
   * Time Complexity O(1)
   * @param {number} i 第i位置的元素
   * @param {number} j 第j位置的元素
   * @return {void}
   */
  swap(i: number, j: number): void {
    if (i < 0 || j < 0 || i >= this.size || j >= this.size) {
      throw new Error('Index is illegal.');
    }
    let temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }

  toString(): string {
    let res = '';
    res += `Array: size = ${this.size}, capacity = ${this.getCapacity()}\n`;
    res += '[';
    for (let i = 0; i < this.size; i++) {
      res += this.data[i];
      if (i !== this.size - 1)
        res += ', '
    }
    res += ']';
    return res;
  }
}

2.Java版本

public class Array<E> {
    private E[] data;
    private int size;

    // 構造函數，傳入數組的容量capacity
    public Array(int capacity) {
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 無參數構造函數，默認數組的容量capacity=10
    public Array() {
        this(10);
    }

    // 構函函數，傳進來的是數組
    public Array(E[] arr) {
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++)
            data[i] = arr[i];
        size = arr.length;
    }

    // 獲取數組中有效元素的個數
    public int getSize() {
        return size;
    }

    // 獲取數組的容量
    public int getCapacity() {
        return data.length;
    }

    // 判斷數組是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // Time Complexity O(1)
    // 向數組的末尾添加一個元素e
    public void addLast(E e) {
        add(size, e);
    }

    // Time Complexity O(n)
    // 向數組的頭部添加一個元素e
    public void addFirst(E e) {
        add(0, e);
    }

    // Time Complexity O(n)
    // 在第index位置插入一個新元素e
    // 均攤時間複雜度
    // 假設capacity=n, 經過n+1次的addLast操作，觸發resize，總共進行2n+1次基本操作
    // 因此平均每次addLast操作，進行2次的基本操作
    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("AddLast failed. Require index >=0 and index <= size");

        // 如果數組已滿，則擴容1倍
        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++;
    }

    // Time Complexity O(1)
    // 獲取index索引位置的元素
    public E get(int index) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    // 獲取數組的第一個元素
    public E getFirst() {
        return get(0);
    }

    // 獲取數組的最後一個元素
    public E getLast() {
        return get(size - 1);
    }

    // Time Complexity O(1)
    // 修改index位置的元素為e
    public void set(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // Time Complexity O(n)
    // 查找數組中是否包含元素e
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    // Time Complexity O(n)
    // 查找數組中元素e所在的索引，如果不存在元素e，就返回-1
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    // Time Complexity O(n)
    // 刪除指定位置index的元素，並返回刪除的元素
    public E remove(int index) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];

        size--;
        data[size] = null;

        // 當size == capacity / 4時，才將capacity減半。防止複雜度震蕩
        // data.length != 0 是因為不能常見capacity為0的數組
        if (size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }

    // Time Complexity O(n)
    // 從數組中刪除第一個元素，並返回刪除的元素
    public E removeFirst() {
        return remove(0);
    }

    // Time Complexity O(1)
    // 從數組中刪除最後一個元素，並返回刪除的元素
    public E removeLast() {
        return remove(size - 1);
    }

    // Time Complexity O(n)
    // 從數組中刪除元素e
    public void removeElement(E e) {
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    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 void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");
        E ret = data[i];
        data[i] = data[j];
        data[i] = ret;
    }

    // 覆蓋父類的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();
    }
}

更多數據結構和leetcode解法問題，請參考我的github//github.com/GuoLizhi/algorithm