Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.
先给出二维矩阵的行列值，之后再给出一系列操作数目，每个操作是在一个位置插入岛屿。和Number of Islands这种先给出全部岛屿布图不一样，这种情景下更适合使用并查集，因为预先给出岛屿分布，还是无法确定操作的数目，需要扫描二维矩阵，判断为1的地方进行操作。反而使用DFS更方便一些。这题每次加入一个一个岛屿相当于新加入一个集合。之后判断这个新加岛屿上下左右是否有岛屿，如果存在的话，进行集合的合并，把当前岛屿加入，并减少岛屿的个数。
# Definition for a point. # class Point: # def __init__(self, a=0, b=0): # self.x = a # self.y = b class Solution: # @param {int} n an integer # @param {int} m an integer # @param {Pint[]} operators an array of point # @return {int[]} an integer array def numIslands2(self, n, m, operators): if not m or not n or not operators: return [] UF = UnionFind() res = [] for p in map(lambda a: (a.x, a.y), operators): UF.add(p) for dx in (1, 0), (0, 1), (-1, 0), (0, -1): q = (dx[0] + p[0], dx[1]+p[1]) if q in UF.id: UF.union(p,q) res += [UF.count] return res class UnionFind(object): def __init__(self): self.id = {} #object self.sz = {} #object'weight, size here. self.count = 0 def add(self, p): self.id[p] = p self.sz[p] = 1 self.count += 1 def find(self, i): while i!= self.id[i]: self.id[i] = self.id[self.id[i]] ＃路径压缩 i = self.id[i] return i def union(self, p, q): i = self.find(p) j = self.find(q) if i == j: return if self.sz[i] > self.sz[j]: #union is only operated on heads按秩合并 i, j = j, i self.id[i] = j self.sz[i] += self.sz[j] self.count -= 1
以上操作的最多合并次数为4k次，object k个。所以时间复杂度为O((4k+k)log*k).log*为迭代次数，不超过5，所以时间复杂度为O(k)大小。空间复杂度为两个dict（权重和father），O(k)大小。由于key值是tuple，空间消耗非常大，所以这种解法在lintcode上MLE. 可以每次将二维坐标转化为一维坐标来做键值。
Leetcode版本解法: 二维坐标转化为一维数字的表达,一定要注意乘的是列数不是行数!!
class Solution(object): def numIslands2(self, m, n, positions): """ :type m: int :type n: int :type positions: List[List[int]] :rtype: List[int] """ #union find method #union find init function, find function, union function,add function the basic architecture is hashmap. #extra space-saving method, turn the 2D coordinates into 1D, multiply the number of column not row res = [] delta = [1,0,-1,0,1] UF = UnionFind() for a in positions: UF.add(a[0]*n + a[1]) for i in xrange(4): x = a[0] + delta[i] y = a[1] + delta[i+1] p = x*n+y if 0 <= x < m and 0 <= y < n and p in UF.root: UF.union(a[0]*n + a[1], p) res.append(UF.cnt) return res class UnionFind(object): def __init__(self): self.root = {} self.sz = {} self.cnt = 0 def add(self, x): self.root[x] = x self.sz[x] = 1 self.cnt += 1 def find(self, x): #find the root of a node while x!= self.root[x]: self.root[x] = self.root[self.root[x]] x = self.root[x] return x def union(self, x, y): #attention, just union the big brother, link smaller union to the larger one i = self.find(x) j = self.find(y) if i != j: #not in the same union if self.sz[i] > self.sz[j]: self.root[j] = i self.sz[i] += self.sz[j] else: self.root[i] = j self.sz[j] += self.sz[i] self.cnt -= 1