LintCode 題解丨FLAG大廠經典面試題：島嶼的個數II

給定 n, m, 分别代表一個二維矩陣的行數和列數, 并給定一個大小為 k 的二進制數組A. 初始二維矩陣全0. 二進制數組A内的k個元素代表k次操作, 設第i個元素為 ​(A[i].x, A[i].y)​, 表示把二維矩陣中下标為A[i].x行A[i].y列的元素由海洋變為島嶼. 問在每次操作之後, 二維矩陣中島嶼的數量. 你需要傳回一個大小為k的數組.

設定0表示海洋, 1代表島嶼, 并且上下左右相鄰的1為同一個島嶼.

線上評測位址：

LintCode 領扣

​

樣例 1:

輸入: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]

輸出: [1,1,2,2]

解釋:

1. 00000

   00000
   00000
   00000           

2. 01000
   00000
   00000           

3. 01000

   01000
   00000
   00000           

4. 01000
   00000
   00010           

5. 01000
   00000
   00011           

   樣例 2:

輸入: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]

方法一：暴力做法

每次操作後做一遍bfs

枚舉之前未通路過的島嶼，島嶼數量加一

壓入隊列中開始bfs

從bfs的隊列中取出隊首，上下左右四個方向擴充那些沒有通路過的島嶼，擴充之後壓入隊列中

重複執行第四步，一直到隊列為空

這樣從一個島嶼出發，搜尋了它能到的所有島嶼，這些島嶼将合并成一個大島嶼

重新回到第二步

方法二：并查集維護

并查集是指用集合裡的一個元素來當這個集合的代表元

如果兩個元素所在集合的代表元相同，那麼我們就能知道這兩個元素在一個集合當中。

如果我們想合并兩個集合，隻需要把其中一個集合的代表元改為第二個集合的代表元

這道題中，每次将一個海洋i變成一個島嶼i，那麼先将島嶼數量加一

再依次檢視這個島嶼的四周的四個方格

如果相鄰的方格j也是島嶼，那麼先判斷i是不是和j在同一個集合裡

如果不是在一個集合裡，那麼i j所在的兩個集合就是連通的，可以合并算為一個集合,然後讓島嶼數量-1。

如果已經是在同一個集合裡了，那就不用在進行任何操作

我們隻要讓i所在集合的代表元改為j所在集合的代表元就完成了合并操作。

注意：資料中有可能多次将一個位置變成島嶼，第一次以後的操作都是無效的操作，跳過就好了

注意2：x->x1->x2->x3->x4->x5->x6->........->代表元T

我們在第一次尋找x的代表元的回溯的時候

順便把這條路徑的所有xi的父親改為了代表元T

這樣我們以後再次通路x....x6....T這條鍊上的内容時候就可以很快的得到答案

//僞代碼for i 1:n

fa[i]=i //僞代碼，一開始讓所有的父親都是本身

//我們規定代表元的父親為本身，如果一個節點的父親不是本身，說是它在一個元素個數大于1的集合中，而且這個節點并不是代表元

function find(x) //尋找x所在集合的代表元

if(fa[x]==x)

return x; //x是代表元，直接傳回

else

return fa[x]=find(fa[x]) //x不是代表元，尋找x的父親的代表元是誰，并且直接把代表元指派給x的父親

function uniue（x,y）//合并兩個集合

fa[find(x)]=find(y)

複雜度分析

時間複雜度

暴力做法

每次操作都會做一遍bfs ，做一遍bfs的時間複雜度是O(NM)

是以總時間複雜度是 O(KNM)，K是操作次數，NM是地圖長和寬

并查集

每次查詢代表元均攤是O(α) α代表反阿克曼函數，反阿克曼函數是漸進增長很慢很慢的，我們可以近似的認為每次查詢是O(1)的複雜度 我們一共有K次操作，每次操作最多并查集查詢4次，并查集合并4次,是以我們最終的時間複雜度是O(K)的

空間複雜度

n，m是輸入數組 的長和寬

我們需要一個fa數組大小為nm，一個vis數組（标記該點有沒有變成島嶼），是以空間複雜度是O(nm)

public class Solution {

/**
 * @param n: An integer
 * @param m: An integer
 * @param operators: an array of point
 * @return: an integer array
 */

public int find(int []fa, int x) {
    if(x == fa[x]) {
        return x;
    } else {
        return fa[x] = find(fa, fa[x]);
    }
}
public int calc(int x, int y, int n, int m) {
    return x * m + y;
}
public List<Integer> numIslands2(int n, int m, Point[] operators) {

    // write your code here
    List<Integer> ans = new ArrayList<>();
    int [] fa = new int [n * m + 5];
    Map<Integer, Boolean>visited = new HashMap<Integer, Boolean>();
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            fa[calc(i, j, n, m)] = calc(i, j, n, m);
            visited.put(calc(i, j, n, m), false);
        }
    }
    //行走數組，用于周遊i島嶼的四周四個方向的島嶼下标
    int[] zx = {0, 0, 1, -1};
    int[] zy = {1, -1, 0, 0};

    if(operators == null) {
        return ans;
    }
    for(int i = 0; i < operators.length; i++) {

        int x = operators[i].x, y = operators[i].y;
        // 第i次操作的點 已經是島嶼了，跳過就好了
        if(visited.get(calc(x, y, n, m)) == true) {
            ans.add(cnt);
            continue;
        }
        //第i次操作的點 出現了新的島嶼
        cnt++;
        //周遊這個島嶼的四周四個方向
        for(int k = 0; k < 4; k++) {
            int nx = x + zx[k];
            int ny = y + zy[k];
            //判斷往四周走有沒有走越界，或者走到海洋裡，越界或者走到海洋都是沒有的狀态
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited.get(calc(nx, ny, n, m)) == false) {
                continue;
            }
            //判斷四周的島嶼是不是和目前第i次操作的島嶼 已經在一個集合了
            if(find(fa, calc(x, y, n, m)) == find(fa, calc(nx, ny, n, m))) {
                continue;
            }
            /*
            如果不是在一個集合裡，那麼i j所在的兩個集合就是連通的，可以合并算為一個集合,然後讓島嶼數量-1。
            我們隻要讓i所在集合的代表元改為j所在集合的代表元就完成了合并操作
            */
            else {
                cnt--;
                fa[find(fa, calc(x, y, n, m))] = find(fa, calc(nx, ny, n, m));
            }
        }
        //标記它是個島嶼
        visited.put(calc(x, y, n, m), true);
        ans.add(cnt);
    }
    return ans;
}           

}

更多題解參考：

九章算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時線上授課為你傳授面試技巧