[筆記] Master The Coding Interview – 3 @地瓜大的飛翔旅程

章節連結

課程相關資訊
內容

背景知識

範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Array」關於陣列的簡介。

課程對應章節：62~66

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

背景知識

1. Array 陣列，你可以想像成它是一個 List 列表，裡頭的資料依照 Index 有序排列
2. 如果你的需求是要一個個從頭到尾遍歷找東西，那麼這個結構是熱門選項
3. 若對陣列使用 lookup, push 的作法，其時間複雜度為 O(1)
4. 若對陣列使用 insert, delete 的作法，其時間複雜度為 O(n)
5. Dynamic Arrays：跟上述的陣列相比，其長度一開始就是由內部的元素數量設定好的，缺乏彈性。而動態陣列可以根據外部傳入的變數來調整陣列長度，減少多餘的記憶體浪費

範例程式碼

// 建造一個 Dynamic Array，在 ES6 以後，其實沒有想像中難
Array.from({length: 10}) // [undefined, undefined, undefined ......*8]

// 自己建造一個靜態 array
class MyArray {
  constructor(){
     this.length = 0;
     this.data = {};
  }
  get(index){
     return this.data[index];
  }
  push(item){
     this.data[this.length] = item;
     this.length++
     return this.data
  }
  pop(){ // 回傳最後一個元素，並將其從原本的陣列中移除
    const lastItem = this.data[this.length-1];
    delete this.data[this.length-1];
    this.length--;
    return lastItem
  },
  shiftItems(index){
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length-1];
    this.length--
  }
  deleteAtIndex(index){
    // 此方法為 shiftItems 的特別版，會回傳被刪掉的值，且改變陣列長度
    const target = this.data[index];
    this.shiftItems(index);
    return item
  }
}

// 建造一個 Dynamic Array，在 ES6 以後，其實沒有想像中難

Array.from({length: 10}) // [undefined, undefined, undefined ......*8]

// 自己建造一個靜態 array

class MyArray {

constructor(){

this.length = 0;

this.data = {};

}

get(index){

return this.data[index];

}

push(item){

this.data[this.length] = item;

this.length++

return this.data

}

pop(){ // 回傳最後一個元素，並將其從原本的陣列中移除

const lastItem = this.data[this.length-1];

delete this.data[this.length-1];

this.length--;

return lastItem

shiftItems(index){

for (let i = index; i < this.length - 1; i++) {

this.data[i] = this.data[i + 1];

}

delete this.data[this.length-1];

this.length--

}

deleteAtIndex(index){

// 此方法為 shiftItems 的特別版，會回傳被刪掉的值，且改變陣列長度

const target = this.data[index];

this.shiftItems(index);

return item

}