[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)。代码如下：