面試時，follow up 資料量太大的準備方向

目前在準備 FLAG 的 onsite.
地裏面經，
常提到follow-up就是數據很大時候該怎麼處理?
這時候記憶體放不下、無法一次處理完。

舉例: Leetcode 上 Number of Islands   

假設 grids 是超級大的話，
這時候我們可能會切塊處理
每次處理 1k*1k 的dimension,
但是我不太理解 假設我有2份 1k*1k的grids.
假設 原本大棋盤分成 左|右
我要怎麼處理 merge 的步驟?
假設 左邊 處理完有 100個島嶼 右邊 處理完有 200個島嶼。
但是也許他們合併再一起、有些島嶼又可以被合併了。
所以答案也許是234個島嶼
這邊 merge 的思路，有人有idea嗎?

我甚至還有看過 無窮大的棋盤(grids)
但是沒印象看到該如何解決無窮大的問題。

Thanks~

我不知道这个思路行不行：

如果每个unit记录边界。0表示是unit内部的，具体什么值不是下图表示的重点。X是该unit的边界。表示parent的id。然后四个个unit通过合并内部边界得到一个大的unit。大的unit也有4倍长的边界。recusively和更多的合并。因为边界也会越来越大，类似的做法可以应用到边界的合并上。

1.   X X
   
2. X 0 0 X
   
3. X 0 0 X
   
4.   X X

复制代码

四连通的话，左grid右edge与右grid左edge求交，转化为1k的vector上求连通区域数n，然后100+200-n

持续关注一波

马克一下

递归 变迭代 分解 等等

tomato217 发表于 2019-2-14 15:19
四连通的话，左grid右edge与右grid左edge求交，转化为1k的vector上求连通区域数n，然后100+200-n

就是union-find

马克 持续关注。经常问到

马克一下