題目
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
Challenge:
Can you do it in time complexity O(k log mn), where k is the length of the positions?
解題之法
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> res;
if (m <= 0 || n <= 0) return res;
vector<int> roots(m * n, -1);
int cnt = 0;
vector<vector<int> > dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (auto a : positions) {
int id = n * a.first + a.second;
roots[id] = id;
++cnt;
for (auto d : dirs) {
int x = a.first + d[0], y = a.second + d[1];
int cur_id = n * x + y;
if (x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1) continue;
int new_id = findRoots(roots, cur_id);
if (id != new_id) {
roots[id] = new_id;
id = new_id;
--cnt;
}
}
res.push_back(cnt);
}
return res;
}
int findRoots(vector<int> &roots, int id) {
while (id != roots[id]) {
roots[id] = roots[roots[id]];
id = roots[id];
}
return id;
}
};
分析
這道題是之前那道Number of Islands的拓展蜡镶，難度增加了不少雾袱，因?yàn)檫@次是一個(gè)點(diǎn)一個(gè)點(diǎn)的增加，每增加一個(gè)點(diǎn)官还，都要統(tǒng)計(jì)一下現(xiàn)在總共的島嶼個(gè)數(shù)芹橡。
那么我們?yōu)榱私鉀Q這種陸地之間會(huì)合并的情況，最好能夠?qū)⒚總€(gè)陸地都標(biāo)記出其屬于哪個(gè)島嶼望伦，這樣就會(huì)方便我們統(tǒng)計(jì)島嶼個(gè)數(shù)林说，于是我們需要一個(gè)長(zhǎng)度為m*n的一維數(shù)組來標(biāo)記各個(gè)位置屬于哪個(gè)島嶼，我們假設(shè)每個(gè)位置都是一個(gè)單獨(dú)島嶼屯伞，島嶼編號(hào)可以用其坐標(biāo)位置表示腿箩，但是我們初始化時(shí)將其都賦為-1，這樣方便我們知道哪些位置尚未開發(fā)劣摇。然后我們開始遍歷陸地?cái)?shù)組珠移，將其島嶼編號(hào)設(shè)置為其坐標(biāo)位置，然后島嶼計(jì)數(shù)加1，我們此時(shí)開始遍歷其上下左右的位置钧惧，遇到越界或者島嶼標(biāo)號(hào)為-1的情況直接跳過暇韧，否則我們來查找鄰居位置的島嶼編號(hào)，如果鄰居的島嶼編號(hào)和當(dāng)前點(diǎn)的編號(hào)不同浓瞪，說明我們需要合并島嶼锨咙，將此點(diǎn)的編號(hào)賦為鄰居的編號(hào)，在編號(hào)數(shù)組里也要修改追逮，并將島嶼計(jì)數(shù)cnt減1。當(dāng)我們遍歷完當(dāng)前點(diǎn)的所有鄰居時(shí)粹舵，該合并的都合并完了钮孵，將此時(shí)的島嶼計(jì)數(shù)cnt存入結(jié)果中。
注意在查找島嶼編號(hào)的函數(shù)中我們可以做路徑壓縮Path Compression眼滤，只需加上一行roots[id] = roots[roots[id]];這樣在編號(hào)數(shù)組中巴席，所有屬于同一個(gè)島嶼的點(diǎn)的編號(hào)都相同，可以自行用上面的那個(gè)例子來一步一步的走看roots的值的變化過程:
roots:
-1 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1 -1
0 -1 2 -1 -1 -1 -1 -1 -1
2 0 2 -1 -1 -1 -1 -1 -1
2 2 2 -1 2 -1 -1 -1 -1