0305._Number_of_Islands_II.md

305. Number of Islands II

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/number-of-islands-ii/description/

内容描述

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:

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]
Explanation:

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
Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

解题方案

思路 1

对于positions中的每一个点，我们把他认为是一个单独的岛屿的root，然后我们看看他周围有没有value为1的点（即陆地），如果有，那么那一块陆地的root也是当前点

然后每次结束一个点，我们就可以算一下当前一共有几个岛屿，即有几个不同的root，在代码中为island_groups的长度

这个解法也称为并查集算法，可以去看看union-find

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        # find the root of a point
        def find(x, uf):
            while x != uf[x]:
                uf[x] = uf[uf[x]]
                x = uf[x]
            return uf[x]
        
        island_groups, res, uf, idx = set(), [], {}, 1
        for i, j in positions:
            uf[(i, j)] = uf[idx] = idx
            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                # when neighbor == 1, we make cur_point as the root
                if (x, y) in uf:
                    root = find(uf[(x, y)], uf)
                    island_groups.discard(root)
                    uf[root] = idx
            island_groups.add(idx)
            idx += 1
            res.append(len(island_groups))
        return res

因为并查集的查找时间复杂度是O(lgN)，由于这里N就是m*n，所以我们总的时间复杂度就是O(k*lgmn)