跳至主要内容

[資料結構] 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]));

參考