Google最新面試題
給一個矩陣，其中0代表海洋，其他數(shù)字代表高度，秉著水往低處流的原則，求出能夠流向任意海洋的點。 比如說
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
那么就要給出 第二行的4 (這有這點出發(fā)，能夠找到連通道四個0的區(qū)域的一條非遞增路線)，當(dāng)然也有可能找不到這樣的點，或者找到多個點。
小編解答：
題目類型TAG：
圖論，搜索，并集，擴散染色
一句話思路：
從原題矩陣中建立一個有向圖，其中結(jié)點是矩陣中等高聯(lián)通區(qū)域，而有向邊連接的這些結(jié)點在矩陣中所代表的聯(lián)通區(qū)域相鄰，其方向是從底高度節(jié)點指向高高度結(jié)點;我們從低高度結(jié)點到高高度結(jié)點遍歷整個有向圖，并在遍歷中不斷地對匯入當(dāng)前節(jié)點的海洋節(jié)點求并集;最后包括所有海洋節(jié)點的節(jié)點便是所求的節(jié)點。
詳細步驟：
1. 建立所有有向圖節(jié)點：通過遍歷矩陣，我們可以找到所有的相鄰的高度一樣的區(qū)域。我們把每一個這樣的區(qū)域組成一個有向圖的節(jié)點，用這個區(qū)域的高度來標(biāo)識這個節(jié)點的.高度。要注意的是，我們要在原矩陣的每個元素上記錄其所屬的有向圖節(jié)點，以便于下一步中建立有向邊。這些有向圖的節(jié)點里面還應(yīng)包括一個bitset，以便第三步中進行對其能到達海洋求并集。給每一個高度為0 的有向圖節(jié)點的bitset里面set一個unique 的bit。
2. 建立節(jié)點有向邊: 再次遍歷矩陣，這次注意所遍歷元素的上下左右所有相鄰元素。如果這些相鄰元素和當(dāng)前元素屬于不同有向圖的節(jié)點，則通過有向邊連接他們，邊的方向是由底高度節(jié)點指向高高度節(jié)點。在設(shè)置有向邊的時候，要注意去除重復(fù)的邊。
3. 遍歷有向圖：將有向圖從底到頂遍歷。遍歷的時候，將前導(dǎo)節(jié)點的bitset 并入當(dāng)前節(jié)點，如果當(dāng)前節(jié)點的bitset中包括所有的海洋bits，那么當(dāng)前節(jié)點就標(biāo)記為成功節(jié)點。
4. 得出答案：再一次遍歷原矩陣?yán)锩娴乃性兀绻硞�元素所屬的有向圖節(jié)點是成功節(jié)點，那么這個元素也就是屬于所要找的點。
時間復(fù)雜度分析：
由于步驟1，2，3, 4 的復(fù)雜度都是O(n),n表示矩陣中的元素個數(shù)，那么最后的整體時間復(fù)雜度也是O(n)
http://www.fuchuonang.cn/