[Day 11] 演算法刷題 LeetCode 4. Median of Two Sorted Arrays (Hard)，這題真 d 難，原本隨意想了一下想不出來，後來在火車上沒事做開始認真想，大概有點方向。

原本看到複雜度就猜說應該跟二分搜有點關係，後來發現用類似的思路去想好像行得通。

舉例來說好了，假設現在有這兩個排序好的數列：

A = 1 7 18 20 36 59 72
B = 3 9 33 47 75 80 82 93

先從 A 開始做二分搜，找到中間那個數字 20
所以我們知道，在 A 裡面左邊有 3 個數字比他小，右邊有 3 個數字比他大
如果 A 是 AB 合併後的中位數，那把 B 裡面要有 4 個數字比他小，4 個數字比他大，這樣才能平衡
所以直接看 B 的第四個數字：47

發現 47 比 20 大，代表 20 不可能是中位數，因為在 B 裡面找不到 4 個比他小的數字
而 20 的左邊（1 7 18）也不可能是中位數
因為如果 18 是中位數，代表要能夠在 B 裡面找到 4 個以上的數字比他小，但連 20 都找不到了，何況是比 20 更小的 18？

所以這樣就可以排除這些，把範圍限縮到只剩 36, 59, 72 這三個
二分的複雜度是 O(n)，確認是 O(1)，所以 A 跟 B 各掃一遍之後時間複雜度是 O(log n + log m)，這樣就是 O(log mn)，離題目要求的 O(log(n+m))還有一段距離。

另一個想法是對兩個數列同時做二分搜，一樣以上面的數列為例：

A = 1 7 18 20 36 59 72
B = 3 9 33 47 75 80 82 93

合起來一共 7+8 = 15 個數
中位數會是由小排到大之後第 8 個數

L1=0, R1=6, M1=3, A[3] = 20
L2=0, R2=7, M2=3, B[3] = 47

A 裡面比 20 小的數字有 3 個
假設 B[3] 左邊的數字都小於 20，比 20 小的數字就是 3+3=6 個
所以中位數不可能在 20 左邊，也不可能是 20，一定在 20 右邊

相同地，47 右邊的數有 4 個
假設 A[3] 右邊的數都大於 47，比 47 大的數就是 4+3=7 個
所以中位數不可能出現在 47 右邊

不過一起做的話我就不會算時間複雜度了，而且感覺好像跟上面的做法其實是一樣的？
以後有空再來研究吧

以陣列 Array 的複製談型別（下），deep clone 是一個很好練習遞迴的題目，然後最大的坑在於循環引用（circular reference），一直放在我的待寫清單裡面 ?

[day11] YDKJS (Equality) : 一般相等 == 比較「值」 ， 嚴格相等 === 比較 「型別和值」是錯的？，在 JS 各大重點裡面，型別的轉換一直是我刻意忽略的一部分，因為規則太多 ?
之後想補這塊的時候再來看這個系列文，推推

Day15 | React-Saga 見一次就愛上的 async flows，突然想起來之前面試人的時候如果我看到對方履歷上有寫說用過 redux，就會問他說當時選擇了哪一套 middleware 做非同步的處理。接著會繼續追問說，redux-thunk 跟 redux-saga 的差別在哪邊？

Day26 前端可以不只是前端，之前我都跟我學生說：「不要忘了，前端工程師的全名其實是『網頁前端』工程師，對網頁來說，前後端無論缺了哪一塊都不完整。你若是想理解整個網頁的運作，就必須要懂後端」

今天早上從柏林搭火車到慕尼黑，搭的是德國鐵路(DB)的 ICE（德國高鐵）first class，到柏林車站時可以先進 DB lounge，在裡面喝了一杯柳橙汁還有吃了個三明治：

座位是 1 2，我記得台灣高鐵商務艙好像是 2 2，但我覺得 DB 有點晃就是了，有 wifi 但速度很不穩定，好像也滿正常的，速度快就會這樣。搭起來覺得高鐵商務艙比這個厲害，還有免費的飲料跟餅乾可以拿，ICE 也有啦，但只有巧克力跟餅乾。一共快五小時的車程，一個半小在睡覺，另外就是發呆、上網、想上面那一個題目。

到慕尼黑之後立刻就發現人好多，搭著 U1 前往住處，出了地鐵站之後要走個大概十分鐘，但還是挺 ok 的。明天沒意外的話要跟兩個老朋友見面，讚讚讚