Java中如何删除二维数组中除最大岛外的其余数字岛？

我正在实现一个Java方法，该方法接收二维数组，扫描数组找出被0完全包围的数字块（我称之为“岛”），并将除最大岛之外的所有岛转换为0。

示例 #

原数组：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 1 2 0
0 0 0 0 0 0 

处理后：

1 2 3 2 2 1 
3 2 2 1 2 3
3 2 2 1 3 2
2 3 2 3 2 2
2 2 3 1 1 2
3 2 1 2 3 2
2 3 1 2 3 2
2 2 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 

其中小块1 2被置为0。

另外，边缘的独立数字岛也需要删除，仅保留最大岛。

当前代码问题 #

现有代码会将所有数字块识别为岛并全部置0，而非仅删除小岛。代码如下：

public class destroyIslands {
    public static void main(String[] args) {
        int[][] example = { {1, 2, 3, 1, 2},
                            {2, 3, 2, 1, 2},
                            {3, 2, 1, 2, 2},
                            {0, 2, 0, 0, 0},
                            {0, 0, 0, 2, 1} };
        
        example = deleteIslandBoard(example);
        printGrid(example);
    }
    
    public static int[][] deleteIslandBoard(int[][] array) {
      // Create a boolean array to track which cells have been visited
      boolean[][] visited = new boolean[array.length][array[0].length];
    
      // Iterate 
      for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[0].length; j++) {
            // If the cell is not visited and is part of an island
            if (!visited[i][j] && array[i][j] != 0) {
                // Delete the island by setting all cells to 0
                deleteIsland(array, i, j, visited);
            }
        }
      }
      // Return the modified array
      return array;
    }

    public static void deleteIsland(int[][] array, int i, int j, boolean[][] visited) {
      // Check if the current cell is out of board or if it has already been visited
      if (i < 0 || i >= array.length || j < 0 || j >= array[0].length || visited[i][j]) {
        return;
      }
      // Mark the current cell as visited
      visited[i][j] = true; // If the current cell is part of the island, set it to 0
      if (array[i][j] != 0) {
        array[i][j] = 0;
        // Recursively delete the neighboring cells that are part of the island
        deleteIsland(array, i - 1, j, visited);
        deleteIsland(array, i + 1, j, visited);
        deleteIsland(array, i, j - 1, visited);
        deleteIsland(array, i, j + 1, visited);
      }
    }
    
    public static void printGrid(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

修改方案 #

需要分三个阶段处理：收集所有岛的信息、找出最大岛、删除非最大岛，具体修改如下：

1. 新增数据结构存储岛信息 #

创建内部类存储每个岛的单元格坐标列表和大小：

static class Island {
    List<int[]> cells;
    int size;

    Island() {
        cells = new ArrayList<>();
        size = 0;
    }
}

2. 替换删除逻辑为收集岛信息 #

修改deleteIslandBoard方法，先遍历数组收集所有岛的信息，再处理删除：

public static int[][] deleteIslandBoard(int[][] array) {
    boolean[][] visited = new boolean[array.length][array[0].length];
    List<Island> islands = new ArrayList<>();

    // 收集所有岛的信息
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[0].length; j++) {
            if (!visited[i][j] && array[i][j] != 0) {
                Island island = new Island();
                collectIsland(array, i, j, visited, island);
                islands.add(island);
            }
        }
    }

    // 找出最大岛的面积
    int maxSize = 0;
    for (Island island : islands) {
        if (island.size > maxSize) {
            maxSize = island.size;
        }
    }

    // 删除所有非最大的岛
    for (Island island : islands) {
        if (island.size != maxSize) {
            for (int[] cell : island.cells) {
                array[cell[0]][cell[1]] = 0;
            }
        }
    }

    return array;
}

3. 新增收集岛信息的递归方法 #

替换原deleteIsland方法为collectIsland，只收集坐标不修改数组：

public static void collectIsland(int[][] array, int i, int j, boolean[][] visited, Island island) {
    if (i < 0 || i >= array.length || j < 0 || j >= array[0].length || visited[i][j] || array[i][j] == 0) {
        return;
    }

    visited[i][j] = true;
    island.cells.add(new int[]{i, j});
    island.size++;

    // 递归遍历上下左右连通单元格
    collectIsland(array, i - 1, j, visited, island);
    collectIsland(array, i + 1, j, visited, island);
    collectIsland(array, i, j - 1, visited, island);
    collectIsland(array, i, j + 1, visited, island);
}

4. 完整修改后的代码 #

import java.util.ArrayList;
import java.util.List;

public class destroyIslands {
    static class Island {
        List<int[]> cells;
        int size;

        Island() {
            cells = new ArrayList<>();
            size = 0;
        }
    }

    public static void main(String[] args) {
        int[][] example = { {1, 2, 3, 1, 2},
                            {2, 3, 2, 1, 2},
                            {3, 2, 1, 2, 2},
                            {0, 2, 0, 0, 0},
                            {0, 0, 0, 2, 1} };
        
        example = deleteIslandBoard(example);
        printGrid(example);
    }
    
    public static int[][] deleteIslandBoard(int[][] array) {
        boolean[][] visited = new boolean[array.length][array[0].length];
        List<Island> islands = new ArrayList<>();

        // 收集所有岛的信息
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                if (!visited[i][j] && array[i][j] != 0) {
                    Island island = new Island();
                    collectIsland(array, i, j, visited, island);
                    islands.add(island);
                }
            }
        }

        // 找出最大岛的面积
        int maxSize = 0;
        for (Island island : islands) {
            if (island.size > maxSize) {
                maxSize = island.size;
            }
        }

        // 删除所有非最大的岛
        for (Island island : islands) {
            if (island.size != maxSize) {
                for (int[] cell : island.cells) {
                    array[cell[0]][cell[1]] = 0;
                }
            }
        }

        return array;
    }

    public static void collectIsland(int[][] array, int i, int j, boolean[][] visited, Island island) {
        if (i < 0 || i >= array.length || j < 0 || j >= array[0].length || visited[i][j] || array[i][j] == 0) {
            return;
        }

        visited[i][j] = true;
        island.cells.add(new int[]{i, j});
        island.size++;

        // 递归遍历上下左右连通单元格
        collectIsland(array, i - 1, j, visited, island);
        collectIsland(array, i + 1, j, visited, island);
        collectIsland(array, i, j - 1, visited, island);
        collectIsland(array, i, j + 1, visited, island);
    }
    
    public static void printGrid(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

逻辑说明 #

1. 收集阶段：遍历数组，遇到未访问的非0单元格时，递归遍历其上下左右的连通单元格，记录所有属于该岛的坐标和大小。
2. 找最大岛：遍历所有收集到的岛，记录最大的面积。
3. 删除阶段：遍历所有岛，把面积不等于最大面积的岛的所有单元格置为0。

这样就能实现只保留最大岛，其余小岛全部删除的需求。

内容的提问来源于stack exchange，提问作者MazaPan616