[LeetCode]Number of Islands II

II的题目变为了每加一个1再看现在有多少个岛屿。很显然我们不能再用dfs了，不然每一次add的操作我们都要dfs整个2D array，非常不效率。这个时候我们就要考虑相应的数据结构了，我们可以使用Union Find，Union Find是支持链接元素和查询任意元素是否链接的数据结构，具体的细节可以参考这篇文章。我们只需要对其稍加修改，让它能够记录每个时刻连通岛屿的数量即可。Union Find支持的操作union 和 find的时间复杂度都十分接近常数时间，那么整个算法的时间复杂度也就趋近与O(positions)。空间复杂度O(m * n)。代码如下：

	class UnionFind
	{
	public:
	UnionFind(int n)
	{
	m_v = vector<int>(n, -1);
	m_sz = vector<int>(n, 0);
	comps = 0;
	}
	void Add(int i, int j, int m, int n)
	{
	int idx = i * n + j;
	m_v[idx] = idx;
	m_sz[idx] = 1;
	++comps;
	vector<pair<int, int>> dirs = {{1, 0},{-1, 0},{0, 1},{0, -1}};
	for(auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x >= 0 && x < m && y >= 0 && y < n && m_v[x * n + y] != -1)
	connect(idx, x * n + y);
	}
	}
	int NumOfComps()
	{
	return comps;
	}
	private:
	vector<int> m_v;
	vector<int> m_sz;
	int comps;
	int root(int i)
	{
	if(i == m_v[i])
	return i;
	int r = root(m_v[i]);
	m_v[i] = r;
	return r;
	}
	void connect(int i, int j)
	{
	int root1 = root(i), root2 = root(j);
	if(root1 != root2)
	{
	if(m_sz[root1] >= m_sz[root2])
	{
	m_v[root2] = root1;
	m_sz[root1] += m_sz[root2];
	}
	else
	{
	m_v[root1] = root2;
	m_sz[root2] += m_sz[root1];
	}
	--comps;
	}
	}
	};
	class Solution {
	public:
	vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
	vector<int> res;
	UnionFind uf(m * n);
	for(auto& p : positions)
	{
	uf.Add(p.first, p.second, m, n);
	res.push_back(uf.NumOfComps());
	}
	return res;
	}
	};

view raw Number of Islands II.cpp hosted with ❤ by GitHub