【Leetcode】827. Making A Large Island_综合

题目地址：

https://leetcode.com/problems/making-a-large-island/

给定一个二维 $0 ? 1$ 矩阵，允许将其中的某一个 $0$ 变为 $1$ ，问能得到的最大的 $1$ 连通块的面积（即 $1$ 的数量）。

法1：并查集。这个问题的关键在于，当遍历到 $0$ 的时候，将其变为 $1$ 之后连通了其的四个邻居，但不知道这四个邻居是属于不同连通块的还是属于相同连通块的，如果属于相同连通块，就会造成重复计算的问题。这时候并查集可以解决这个问题，当两个节点在并查集的树的祖宗节点相等，就说明它们是属于同一个连通块的。这样就能避免重复计算。同时也需要注意矩阵全是 $1$ 的情况，这时直接返回矩阵的面积即可。代码如下：

import java.util.*;public class Solution {
    class Pair {
    int x, y;public Pair(int x, int y) {
    this.x = x;this.y = y;}@Overridepublic boolean equals(Object o) {
    Pair pair = (Pair) o;return x == pair.x && y == pair.y;}@Overridepublic int hashCode() {
    return Objects.hash(x, y);}}class UnionFind {
    Map<Pair, Pair> parent;Map<Pair, Integer> size;public UnionFind() {
    parent = new HashMap<>();size = new HashMap<>();}public void add(Pair x) {
    if (!parent.containsKey(x)) {
    parent.put(x, x);size.put(x, 1);}}// 找到x的祖宗节点public Pair find(Pair x) {
    add(x);if (!x.equals(parent.get(x))) {
    parent.put(x, find(parent.get(x)));}return parent.get(x);}public void union(Pair x, Pair y) {
    Pair px = find(x), py = find(y);if (px.equals(py)) {
    return;}parent.put(px, py);size.put(py, size.get(px) + size.get(py));}public int getSize(Pair x) {
    return size.get(find(x));}}public int largestIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;UnionFind uf = new UnionFind();for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    // 接下来将1连通块都union起来if (grid[i][j] == 1) {
    Pair cur = new Pair(i, j);uf.add(cur);int[] d = {
    1, 0, -1, 0, 1};for (int k = 0; k < 4; k++) {
    int nextI = i + d[k], nextJ = j + d[k + 1];if (0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n && grid[nextI][nextJ] == 1) {
    Pair next = new Pair(nextI, nextJ);uf.union(cur, next);}}}}}int res = 0;// 记录有没有找到0boolean found = false;for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (grid[i][j] == 0) {
    found = true;Set<Pair> set = new HashSet<>();int area = 1;int[] d = {
    1, 0, -1, 0, 1};for (int k = 0; k < 4; k++) {
    int nextI = i + d[k], nextJ = j + d[k + 1];if (0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n && grid[nextI][nextJ] == 1) {
    Pair next = new Pair(nextI, nextJ);// 找到邻居的祖宗，相同祖宗的邻居的1连通块面积只算1次Pair ancestor = uf.find(next);if (!set.contains(ancestor)) {
    area += uf.getSize(ancestor);set.add(ancestor);}}}res = Math.max(res, area);}}}return found ? res : m * n;}
}

时间复杂度 $O(mn\log ^* (mn))$ ，空间 $O (m n)$ 。

注解：这个方法虽然容易想到，但哈希表的put非常耗时。数组并查集的版本可以参考https://blog.csdn.net/qq_46105170/article/details/109178762。

法2：BFS + 标记连通块编号。思路是将每个 $1$ 连通块编上号，并且用哈希表存一下每个编号对应的 $1$ 连通块的面积。这样只需要保证相同编号的 $1$ 连通块的面积不要累加两次就行了。标记 $1$ 连通块的过程可以用BFS来实现（当然DFS也可以，参考https://blog.csdn.net/qq_46105170/article/details/109178762）。代码如下：

import java.util.*;public class Solution {
    public int largestIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;int[][] ids = new int[m][n];boolean[][] visited = new boolean[m][n];// 存编号为key的1连通块的面积Map<Integer, Integer> map = new HashMap<>();for (int i = 0, id = 1; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (!visited[i][j] && grid[i][j] == 1) {
    map.put(id, bfs(i, j, id, ids, grid, visited));id++;}}}int res = 0;boolean found = false;int[] d = {
    1, 0, -1, 0, 1};for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (grid[i][j] == 0) {
    found = true;int area = 1;Set<Integer> set = new HashSet<>();for (int k = 0; k < 4; k++) {
    int nextI = i + d[k], nextJ = j + d[k + 1];if (inBound(nextI, nextJ, grid) && grid[nextI][nextJ] == 1) {
    int id = ids[nextI][nextJ];// 相同id的连通块面积只累加一次if (!set.contains(id)) {
    area += map.get(id);set.add(id);}}}res = Math.max(res, area);}}}return found ? res : m * n;}// 对(x, y)所在的1连通块做BFS，返回其面积，同时将该连通块的编号填充为idprivate int bfs(int x, int y, int id, int[][] ids, int[][] grid, boolean[][] visited) {
    visited[x][y] = true;ids[x][y] = id;int area = 0;Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{
    x, y});int[] d = {
    1, 0, -1, 0, 1};while (!queue.isEmpty()) {
    area++;int[] cur = queue.poll();for (int i = 0; i < 4; i++) {
    int nextX = cur[0] + d[i], nextY = cur[1] + d[i + 1];if (inBound(nextX, nextY, grid) && grid[nextX][nextY] == 1 && !visited[nextX][nextY]) {
    // 填充idids[nextX][nextY] = id;visited[nextX][nextY] = true;queue.offer(new int[]{
    nextX, nextY});}}}return area;}private boolean inBound(int x, int y, int[][] grid) {
    return 0 <= x && x < grid.length && 0 <= y && y < grid[0].length;}
}

时空复杂度 $O (m n)$ 。