iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 6
3

前面說了這麼多,終於可以來刷 LeetCode 了! 像 前一章 說的,刷題沒有任何第三方工具可以使用,必須對語法本身相當熟練(例如 javaScript)。所以這一系列我都會先介紹某個演算法/資料結構概念再進行刷題,今天要刷 Array,所以若沒有看過之前的文章沒關係,但至少要看這篇 陣列 Array


905. Sort Array By Parity

題目連結在此

/*
Given an array A of non-negative integers, 
return an array consisting of all the even elements of A, 
followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

input: 給一個沒有負數的數字陣列
output: 回傳前面是偶數後面是奇數的陣列

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000
*/

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function(A) {
  
};

個人英文也不是高手無法馬上就 100% 理解題目。所以我看完題目後,會更認真看範例從中再回去理解題目是什麼。例如忘了 odd 跟 even 哪個是奇數哪個偶數,看範例就很容易得到解答

Output: [2,4,3,1]  → 先偶數 (even) 再奇數 (odd)

Think

極限值/特殊狀況

  • 可能會有一樣的值 [1, 2, 1]
  • 如果只有一個值 [1]
  • 值不是數字 ( 但題目已經說一定是數字所以這種狀況就不用再判斷了 )

哪種資料結構解

  • 這題很容易想,題目有 Array 又跟排序有關,那當然就是 Array 了

大概會怎麼解

這邊通常會想完之後再打掉,想完再打掉,直到覺得可行再來寫。當然也是可以邊寫邊想啦!
https://ithelp.ithome.com.tw/upload/images/20190907/20106426znlrHO2FVP.jpg

  • Array 遍歷ㄧ次,發現偶數就從前面放,奇數就從後面放
// 大概是這種概念
[3, 1, 2, 4]

    [ ] ← 3
    [3] ← 1
2 → [3, 1] 
4 → [2, 3, 1]

[4, 2, 3, 1]

用程式實踐

var sortArrayByParity = function(A) {
  // 先處理極限值
  if(A.length < 2){
		return A
	};
  // 把想法變成程式碼實踐
  let temp = []
  A.forEach( item => {
    item%2==0 ? temp.unshift(item) : temp.push(item)
  })
  return temp
};

Array 遍歷ㄧ次,所以時間複雜度是 Big O(n)


561. Array Partition I

題目連結在此

/*
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

input: 給一個偶數的陣列
output: 回傳 min(a1, b1) + ... min(ai, bi) 的最大值
這種中文好難翻譯,先看範例會比較清楚

Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
*/

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
  
};

Think

極限值/特殊狀況

  • 有排序嗎?看起來是沒有

哪種資料結構解

  • 一樣是 Array,然後會用到 Math.min()

大概會怎麼解

  • 我知道加總起來要得到最大值,就是小的跟小的在一起,大的跟大的再一起。所以首先要先排序 (很多題目都要先排序再做),然後依序加起來。

用程式實踐

var arrayPairSum = function(nums) {
    const len = nums.length;
    let result = 0;
    nums = nums.sort((a,b) => a-b);
    for(let i= 0; i < len; i += 2){
        result += Math.min(nums[i], nums[i+1])
    }

    return result;
};

這題時間複雜度是 Big O(nlogn) (謝謝邦友 huli 更正指教)


這邊只是簡單分享個人思考題目的過程而已,畢竟 LeetCode 需要實際練習才能知道箇中滋味。而 Array 其實相當重要也是最好入門的題目之一 (好歹平常專案還是會碰到的)。他相關題目可是有高達 192 題呢 (而且應該會越來越多 ... )。

下一篇會來介紹跟 Array 不太一樣的資料結構 Set


上一篇
[番外篇] 解 LeetCode 之前
下一篇
集合 Set
系列文
前端工程師用 javaScript 學演算法32

2 則留言

0
huli
iT邦新手 5 級 ‧ 2019-09-07 23:51:53

Array Partition I 那題時間複雜度不是 O(n) 喔,因為有用到排序了,所以應該是 O(nlogn)

看更多先前的回應...收起先前的回應...
huli iT邦新手 5 級 ‧ 2019-09-08 00:19:48 檢舉

然後第一題的解法有點小奇怪

奇怪的第一個點是針對 A.length < 2 的情形,應該不用特別做處理。第二個點是 filter 不該這樣用,如果是面試的話應該會被問說:「為什麼這邊要用 filter?」,比較好的做法是用 foreach 或是 for loop 就好,因為你本來的目的就是遍歷陣列,而不是想要過濾掉東西。

hannahpun iT邦新手 5 級 ‧ 2019-09-08 00:53:07 檢舉

謝謝建議 對我的確寫錯了不應該是 filter 是 forEach,這樣時間複雜度應該就是 Big O(n) 了

huli iT邦新手 5 級 ‧ 2019-09-08 01:11:42 檢舉

我說的其實是不同題XD

時間複雜度我講的是第二題 561. Array Partition I 這個,原文裡面寫:「時間複雜度是 Big O(n),因為時間複雜度會忽略所有係數。」,但要注意的是這一題是「先排序過後」才解的,排序本身的時間複雜度就是 O(nlogn)了,所以整個解法的複雜度就是 O(nlogn)

hannahpun iT邦新手 5 級 ‧ 2019-09-08 01:31:38 檢舉

原來是我誤會了XD 謝謝

第二題的 561. Array Partition I 其實不用 Math.min(),因為排序過了, index 為偶數的就是比較小的數字

0
evance
iT邦新手 5 級 ‧ 2019-09-10 11:13:33

應該是「奇」數喔

hannahpun iT邦新手 5 級 ‧ 2019-09-10 11:35:01 檢舉

已改 謝謝糾正

我要留言

立即登入留言