跳至主要内容

[資料結構] Array 和 String

Array 的定義​

  • Contiguous area of memory consisting of equal-size elements indexed by contiguous integers. 連續的一段記憶體空間，且有相同大小（size）並帶有索引（index）的元素。
  • Array 有時又稱作 list。
  • 要處理 string 時，要用 array 的角度來思考，string 就是有很多 element 的 string。

Time Complexity​

  • Lookup： O(1)，可以根據 index 很快找到對應的元素
  • Push, Pop：O(1)，要將陣列新增或移除最後一個元素很快
  • Insert：O(n)，需要將陣列中的 index 重新排列，會比較慢
  • delete：O(n)，需要將陣列中的 index 重排排列，會比較慢
  • 是有順序性的

Array Methods​

const strings = ['a', 'b', 'c', 'd'];

strings[2]; // O(1)

// push
strings.push('e'); // O(1) | O(n)

// pop
strings.pop(); // O(1)
strings.pop(); // O(1)

// unshift
strings.unshift('x'); // O(n)

// splice
strings.splice(2, 0, 'aaron'); // O(n)

console.log(strings);

Array 的實作​

interface Dictionary<T> {
  [key: number]: T;
}

class MyArray {
  length: number;
  data: Dictionary<any>;

  constructor() {
    this.length = 0;
    this.data = {};
  }

  get(index: number) {
    return this.data[index];
  }

  push(item: any) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  pop() {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }

  delete(index: number) {
    const item = this.data[index];
    this.shiftItems(index);
    this.pop();
    return item;
  }

  shiftItems(index: number) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
  }
}

const newArray = new MyArray();
newArray.push('hi');
newArray.push(',');
newArray.push('how');
newArray.push('are');
newArray.push('you');
newArray.delete(2);
console.log(newArray);

Questions​

reverse string​

思路一：使用交換的方式達到逆排​

將第一個和最後一個元素交換，第二個和倒數第二個交換，以此達到逆排

import { performance } from 'perf_hooks';

const reverse = (str: string) => {
  const t1 = performance.now();
  const characters = str.split('');

  for (let i = 0; i < characters.length / 2; i++) {
    const target = characters[i];
    characters[i] = characters[characters.length - i - 1];
    characters[characters.length - i - 1] = target;
  }
  const t2 = performance.now();
  console.log('cost time :', t2 - t1);

  return characters;
};

思路二：建立新陣列使用 push​

建立一個新陣列，將原陣列的元素從最後方開始 push：

// O(n)：使用 push
const reverse2 = (str: string) => {
  const t1 = performance.now();
  const backward = [];
  const characters = str.split('');

  for (let i = characters.length - 1; i >= 0; i--) {
    backward.push(characters[i]);
  }
  const t2 = performance.now();
  console.log('cost time :', t2 - t1);

  return backward;
};

const longStr = [...Array(100000).keys()].join();
reverse(longStr);
reverse2(longStr);

merge sorted array​

問題：有兩個排序後的陣列，將這兩個陣列合併後，建立一個新的排序好的陣列。​

思路：用兩個指標，依序比較後放入新的陣列​

const mergeSortedArrays = (arr1: number[], arr2: number[]) => {
  const mergedArray = [];
  let i = 0;
  let j = 0;
  let itemOfArr1 = arr1[i];
  let itemOfArr2 = arr2[j];

  // 當 itemOfArr1 或 itemOfArr2 有任何一個是 undefined 就結束迴圈
  while (itemOfArr1 !== undefined && itemOfArr2 !== undefined) {
    // 把 itemOfArr1 或 itemOfArr2 比較小的那個放進到 mergedArray 中
    if (itemOfArr1 <= itemOfArr2) {
      mergedArray.push(itemOfArr1);
      i++;
      itemOfArr1 = arr1[i];
    } else {
      mergedArray.push(itemOfArr2);
      j++;
      itemOfArr2 = arr2[j];
    }
  }

  // 最終 itemOfArr1 或 itemOfArr2 會有一個仍有值（因為沒人和它比），將它放進到 mergedArray 中
  itemOfArr1 && mergedArray.push(itemOfArr1);
  itemOfArr2 && mergedArray.push(itemOfArr2);

  return mergedArray;
};

console.log(mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]));

參考​