iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
11

終於來到資料結構 (Data Structure )第一篇了,相信寫 JS 的人對於 Array 都相當熟悉。那到底什麼是 Array?
https://ithelp.ithome.com.tw/upload/images/20190905/201064264EEnIVs0ur.jpg
簡單來說他就是儲存資料的箱子,而且是連續性的,所以當要拿特定位置的值非常快 array[index]。時間複雜度是 Big O(1) 。但如果你忘了是哪個位置,時間複雜度就會變 Big O(n)。

  • 遇到需要順序的問題,通常 Array 就是最佳解 (例如 Binary Search)。
  • Array 壞處就是當你想要加入某一個值(或移除掉),整個 Array 都會動到 (之後篇章會探討 Array method 的時間複雜度)

這一篇就帶大家複習一次常見的 Array 方法,這些方法會非常頻繁的在 leetcode 用到,所以應該要背的滾瓜爛熟才對。

特別要注意的是

  • 經過 Array 方法後到底回傳了什麼
  • 會不會改變原本的 Array (最後面會整理表格給大家)

如何建立 Array

// 1 literal
// 最常見到也是最推薦的
let arrLiteral = []; // Empty Array
let arrLiteral = [1, 2, 3];
    
// 2 by constructor
// 比較不建議因為效能較差而且會有一些無法預期的結果
// 例如 new Array(3) 會建立 3 個 empty Array
let arrConstructor = new Array() // Empty Array
let arrConstructor = new Array(1, 2, 3)

常見 Array 方法

https://ithelp.ithome.com.tw/upload/images/20190905/20106426psTRBiwFBt.png
上圖是偶然看到 Tommy 大大畫的圖,覺得蠻容易理解的。

Basic Array Method

// 初始值,以下範例都會共用這個 -----
const colors = ['red', 'yellow', 'blue'];

Array.prototype.push(elementN)

在原本的 Array "後面"加上新值,回傳 length。所以把 push 存在變數裡 (newColor) 他竟然會回傳 Array 的長度呢!
另外 const 不能被重新指定值但 colors.push 在這裡卻不會有錯誤,為什麼呢?因為 Array 跟 Object 都是 by reference,只要不是重新指定 ( = ) 就會在同一個 reference 裡。

const newColor = colors.push('purple', 'green');
 
console.log(colors) // ['red', 'yellow', 'blue', 'purple', 'green']
console.log(newColor) // 5

Array.prototype.unshift(elementN)

在原本的 Array "前面"加上新值,且回傳 length

const newColor = colors.unshift('purple', 'green');
 
console.log(colors) // ['purple', 'green', 'red', 'yellow', 'blue' ]
console.log(newColor) // 5

Array.prototype.pop()

移除原本陣列"最後面"的第一個值,回傳被移除掉的那個值

const newColor = colors.pop();
 
console.log(colors) // ['red', 'yellow']
console.log(newColor) // 'blue'

Array.prototype.shift()

移除原本陣列"最前面"的第一個值,回傳被移除掉的那個值

const newColor = colors.shift();
 
console.log(colors) // ['yellow', 'blue' ]
console.log(newColor) // 'red'

Array.prototype.concat()

把兩個陣列合併在一起,並回傳新陣列

const colors2 = ['grey', 'black', 'white'];
const newColor = colors.concat(colors2);
 
console.log(colors) // ['red', 'yellow', 'blue'] 原本的
console.log(newColor) // ['red', 'yellow', 'blue', 'grey', 'black', 'white' ]

Filter/Find something

// 初始值 -----
const inventors = [
    { first: 'Albert', last: 'Einstein', year: 1879, passed: 1955 },
    { first: 'Isaac', last: 'Newton', year: 1643, passed: 1727 },
    { first: 'Galileo', last: 'Galilei', year: 1564, passed: 1642 },
    { first: 'Marie', last: 'Curie', year: 1867, passed: 1934 },
    { first: 'Johannes', last: 'Kepler', year: 1571, passed: 1630 },
    { first: 'Nicolaus', last: 'Copernicus', year: 1473, passed: 1543 },
    { first: 'Max', last: 'Planck', year: 1858, passed: 1947 },
    { first: 'Katherine', last: 'Blodgett', year: 1898, passed: 1979 },
    { first: 'Ada', last: 'Lovelace', year: 1815, passed: 1852 },
    { first: 'Sarah E.', last: 'Goode', year: 1855, passed: 1905 },
    { first: 'Lise', last: 'Meitner', year: 1878, passed: 1968 },
    { first: 'Hanna', last: 'Hammarström', year: 1829, passed: 1909 }
];

Array.prototype.findIndex(item, index, array)

回傳"第一個"符合條件的位置 index,若都找不到則回傳 -1

const findIndexEmpty = inventors.findIndex(function(item){
 
})
console.log(findIndexEmpty) // 沒有找到會回傳 -1
console.log(inventors) // 原本的 array
 
const findIndexInventors = inventors.findIndex(function(item){
    return item.year > 1870;
})
console.log(findIndexInventors) // 0
// 有好幾個是 > 1800 的,但他只會回傳第一個抓到的 index

Array.prototype.find(item, index, array)

回傳一個值,且是"第一個"抓到條件為 true 的值

const findEmpty = inventors.find(function(item){
 
})
console.log(findEmpty) // 沒有條件會 undefined
console.log(inventors) // 原本的 array
 
const findInventors = inventors.find(function(item){
    return item.year > 1870;
})
console.log(findInventors) // 有好幾個是 > 1800 的,但他只會回傳第一個抓到的
// { first: 'Albert', last: 'Einstein', year: 1879, passed: 1955 }

Array.prototype.filter(item, index, array)

回傳一個陣列,只要條件為 true 的就會包含在此陣列,適合拿來搜尋

const filterEmpty = inventors.filter(function(item){
 
})
console.log(filterEmpty) // 沒有條件會 undefined
console.log(inventors) // 原本的 array
 
const filterInventors = inventors.filter(function(item){
    return item.year > 1870;
})
console.log(findInventors)
// [{first: "Albert", last: "Einstein", year: 1879, passed: 1955}
// {first: "Katherine", last: "Blodgett", year: 1898, passed: 1979},
// {first: "Lise", last: "Meitner", year: 1878, passed: 1968}]

Array.prototype.forEach(item, index, array)

forEach 不會回傳任何東西,單純只執行原本陣列裡的事

const forEachInventors = inventors.forEach(function(item){
    return item.year > 1870;
})
console.log(forEachInventors) // undefined, 不會 return 東西
 
inventors.forEach(function(item){
    item.year =  1870;
})
console.log(inventors) // 全部 12 個的 year = 1870

Array.prototype.map(item, index, array)

將條件運算後重新組合回傳一個數量等於 array.length 的陣列

const mapInventors = inventors.map(function(item){
    return item.year > 1870;
})
console.log(mapInventors) // [false, false, true ... 12 個]
console.log(inventors) // 原本的 array
 
const mapInventors2 = inventors.map(function(item){
    if(item.year > 1870){
        return `${item.year}歲`;
    }
    return false;
})
console.log(mapInventors2) // ["1879歲", false, false....]
// 不論是空的或是 false,都會回傳

Array.prototype.some(item, index, array)

回傳一個 Boolean,只要部分符合就回傳 true。它不會 Array 全部找完,只要一找到相符的直就跳出

const someInventors = inventors.some(function(item){
    return item.year > 1870;
})
console.log(someInventors) // true
console.log(inventors) // 原本的 array

Array.prototype.every(item, index, array)

回傳一個 Boolean,需要全部符合才回傳 true,部分符合會回傳 false

const everyInventors = inventors.every(function(item){
    return item.year > 1870;
})
console.log(everyInventors) // false
console.log(inventors) // 原本的 array

Special Method

// 初始值 -----
var special = [8, 0, 14];

Array.prototype.reduce(accumulator, currentValue, currentIndex, array [, initialValue])

回傳運算結果的值。reduce 很特別,他可以與前一個回傳值做運算,先來名詞解釋一下

  • accumulator(前一個回傳的值,從 initialValue 開始.若沒有 initialValue 就是從陣列的 index 0 開始)
  • currentValue 現在的值
  • currentIndex(現在的參數位置)
  • array (全部陣列)
  • initialValue(初始值)
const reduceArray = special.reduce(
function(accumulator, currentValue, currentIndex){
    return Math.max(accumulator, currentValue);
})
console.log(reduceArray) // 14
console.log(special) // 原本的 array

https://ithelp.ithome.com.tw/upload/images/20190905/20106426lMr6paV9yw.png

// 給初始值的狀況
const reduceArray2 = special.reduce(
function(accumulator, currentValue, currentIndex){
    return Math.max(accumulator, currentValue);
},30)
console.log(reduceArray2) // 30

https://ithelp.ithome.com.tw/upload/images/20190909/20106426G1mzVp4XgS.png

Order

Array.prototype.sort(compareFunction)

若沒有 compareFunction,會先自動 .toString() 轉成字串,回傳一個根據 Unicode 排序 array.length 長度的 array 。
特別要提得是,< 10 的 array 會是 stable 排序法, > 10 會是不穩定的排序法。後面篇章會再針對 sort 演算法做說明。

var fruit = ['cherries', 'apples', 'bananas'];
fruit.sort(); // ['apples', 'bananas', 'cherries']
 
var scores = [1, 10, 21, 2];
scores.sort(); // [1, 10, 2, 21]
// 跟你想的不一樣吧,因為 10 是兩個數字組成,
// 在 unicode 裡 32(數字2) > 31(1 開頭的任何數字)
 
var things = ['word', 'Word', '1 Word', '2 Words'];
things.sort(); // ['1 Word', '2 Words', 'Word', 'word']

若有 compareFunction 會有兩個參數 a / b, Array.prototype.sort(a, b)

function compare(a, b) {
  // 若 a 比較小 排序就是 a, b
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  // 若 a 比較大 排序就是 b, a  就是位置會對調
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // 若一樣
  return 0;
}
 
var items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];
 
// sort by value 快速寫法
items.sort(function (a, b) {
  return a.value - b.value;
});
 
// sort by name
items.sort(function(a, b) {
  var nameA = a.name.toUpperCase(); // ignore upper and lowercase
  var nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }
 
  // names must be equal
  return 0;
});

Array.prototype.reverse()

相對單純的一個方法,回傳反過來長度為 array.length 的陣列

var a = ['one', 'two', 'three'];
var reversed = a.reverse();
 
console.log(a);        // ['three', 'two', 'one']
console.log(reversed); // ['three', 'two', 'one']

Operation

// 初始值 -----
const my_array = [5, 1, 3, 8, 6, 0]

Array.prototype.slice(start, end)

slice 就是切,把 array 頭尾切兩刀。回傳在 start(包含) 跟 end 之間的陣列。經過 slice 後原本陣列不會改變

const sliceArray = my_array.slice(2,5);
console.log(sliceArray); // [3, 8, 6]
console.log(my_array); // [5, 1, 3, 8, 6, 0] 不會變

https://ithelp.ithome.com.tw/upload/images/20190905/201064263zvGCXr9qy.png

const sliceArray = my_array.slice(2);
console.log(sliceArray); // [3, 8, 6, 0]

https://ithelp.ithome.com.tw/upload/images/20190905/20106426bgxqWaEq8w.png

const sliceNegativeArray = my_array.slice(-1);
console.log(sliceNegativeArray); // [0]

https://ithelp.ithome.com.tw/upload/images/20190905/20106426LTlhe7kiH2.png

Array.prototype.splice(start, deleteCount, item1, item2, …)

回傳被移掉的值放在陣列裡。splice 乍看下跟 slice 有點像,但其實幾乎完全相反(驚)。slice 是取 start end 裡的東西,而 splice 是 return 中間被移掉的東西。slice 不會影響本來陣列而 splice 會影響原本陣列。新增的 item1、item2 只會影響本來陣列,並不會回傳到新的陣列裡
splice 是拼接的意思你不但可以切掉某塊還可以塞東西進去。

// 假如只有 splice(start),這時會跟 slice 行為一樣
const spliceArray1 = my_array.splice(3)
console.log(spliceArray1); // [8, 6, 0] 被移掉的值
console.log(my_array); // [5, 1, 3],index 3 後面都移掉
 
//一樣可以接受負數
const spliceArray2 = my_array.splice(-1)
console.log(spliceArray2); // [0]
console.log(my_array); // [5, 1, 3, 8, 6] 倒數 1 個後面都移掉
 
// splice(start, deleteCount 抓幾個)
const spliceArray3 = my_array.splice(1, 3)
console.log(spliceArray3); // [1, 3, 8]
console.log(my_array); // [5, 6, 0]
// 從 index 1 開始抓 3 個 把中間值移掉
 
// splice(start, deleteCount 抓幾個, 插入 item)
const spliceArray4 = my_array.splice(1, 3, 'Hana', 'Mike')
console.log(spliceArray4); // [1, 3, 8]
// 不會有 'Hana', 'Mike' 字眼出現
 
console.log(my_array); // [5, "Hana", "Mike", 6, 0]
// 從 index 1 開始抓 3 個 把中間值移掉 並塞進 "Hana", "Mike"

Array.prototype.indexOf(searchElement)

回傳所在位置的 index,如果找不到會回傳 -1

const indexArray = my_array.indexOf(3) // 2
console.log(indexArray) // 2
console.log(my_array) // [5, 1, 3, 8, 6, 0]
 
const indexArray2 = my_array.indexOf(100)
console.log(indexArray) // -1

Array.prototype.join(separator)

把所有陣列裡的值加上 separator,回傳一個字串

const joinArray = my_array.join('-') // 2
console.log(joinArray) // '5-1-3-8-6-0'
console.log(my_array) // [5, 1, 3, 8, 6, 0]
 
const joinArray2 = my_array.join('') // 2
console.log(joinArray2) // '513860'

Array.prototype.includes(searchElement, fromIndex)

看 searchElement 有沒有在 array 裡,回傳 Boolean

const includesArray = my_array.includes(3)
console.log(includesArray) // true
console.log(my_array) // [5, 1, 3, 8, 6, 0]
 
my_array.includes(5,3) // false 從 index 第三個之後找 5

總結

最後做一個表讓自己更清楚
https://ithelp.ithome.com.tw/upload/images/20190905/20106426KHsqUz9TBx.png

今天內容有點多
如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
評量演算法好壞的 Big O
下一篇
[番外篇] 解 LeetCode 之前
系列文
前端工程師用 javaScript 學演算法32
1
Tommy
iT邦新手 5 級 ‧ 2019-09-05 14:45:15

媽,我上別人的鐵人賽了!
這主題太讚了,一定要完賽喔!
加油!

hannahpun iT邦新手 5 級 ‧ 2019-09-05 14:57:08 檢舉

竟然瞬間釣到做圖原作者大大高手

Nacho iT邦新手 5 級 ‧ 2019-11-16 15:38:13 檢舉

樓上兩位圖片整理和詳細說明!!查表複習都好用!

0
chichi
iT邦新手 5 級 ‧ 2019-09-06 09:23:38

期待後續

0
Yu
iT邦新手 4 級 ‧ 2019-09-07 22:12:44

程式碼 const 少了一個c
這邊好像少個c


這邊的 currentValue 應該是 14 (我不確定)


表格整理的很讚

hannahpun iT邦新手 5 級 ‧ 2019-09-09 12:33:11 檢舉

感謝糾正,馬上改

0
Anna Lu
iT邦新手 5 級 ‧ 2019-09-25 12:23:43

很喜歡妳寫的文章,非常淺顯易懂好理解

不過讀到這一段的時候有點跳針 XD
應該是「slice 是取 start end 裡的東西」唷!
https://ithelp.ithome.com.tw/upload/images/20190925/20121560HhVIbD2Fmy.png

hannahpun iT邦新手 5 級 ‧ 2019-09-26 00:20:36 檢舉

對我真的寫錯了 馬上改,謝謝你的糾正

我要留言

立即登入留言