Number of Islands II

这道题因为二维数组的存在，其实用一维数组方式表示的并查集方法不是那么容易想出来，但是并查集并不是只能通过一维数组来表示，哈希表一样可以实现并查集的功能，这里就是利用的tuple结构来表示坐标并进行并查集操作，另外因为是二维，相邻的四个点用了BFS方式来进行，最后额外设置一个当前记录当前集合数的变量来维护，这样可以显著提高效率

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        unionSet = {}
        result = []
        curCount = 0

        for row, col in positions:
            unionSet[(row, col)] = (-1, -1,)
            curCount += 1
            for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                curRow, curCol = row + i, col + j
                if 0 <= curRow < m and 0 <= curCol < n:
                    if (curRow, curCol) in unionSet:
                        a = self.find(unionSet, (curRow, curCol,))
                        b = self.find(unionSet, (row, col,))
                        if a != b:
                            unionSet[a] = b
                            curCount -= 1
            result.append(curCount)

        return result

    def find(self, unionSet, indexTuple):
        if unionSet[indexTuple] == (-1, -1):
            return indexTuple
        unionSet[indexTuple] = self.find(unionSet, unionSet[indexTuple])
        return unionSet[indexTuple]

一维数组的版本搞出来了，其实一维数组最难的地方在临点判断以及一维坐标的具体计算，最后就是相邻合并的问题，这里必须使用一个set来判断，用不等于-1判断相当于没有判断，因为我们并没有一个实际上的棋盘去点这些点

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        parent = [-1] * m * n
        curIsland = 0
        result = []
        store = set()

        for row, col in positions:
            ondDimensionIndex = row * n + col
            curIsland += 1
            store.add(ondDimensionIndex)
            for i, j in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                curRow, curCol = row + i, col + j
                curIndex = curRow * n + curCol
                if 0 <= curRow < m and 0 <= curCol < n and curIndex in store:
                    a = self.find(curIndex, parent)
                    b = self.find(ondDimensionIndex, parent)
                    if a != b:
                        parent[a] = b
                        curIsland -= 1
            result.append(curIsland)
        return result

    def find(self, node, parent):
        if parent[node] == -1:
            return node
        parent[node] = self.find(parent[node], parent)
        return parent[node]