golang 解法, 执行用时: 96 ms, 内存消耗: 9.1 MB, 提交时间: 2022-11-29 12:28:03

var x, y []int
func pondSizes(land [][]int) []int {
    x = []int{-1, 0, 1}
    y = []int{-1, 0, 1}
    m, n := len(land), len(land[0])
    res := make([]int, 0)
    for i, v := range land{
        for j, vv := range v{
            if vv == 0{
                land[i][j] = 1
                sum := 1
                dfs(land, &sum, i, j,m,n)
                res = append(res, sum)
            }
        }
    }
    sort.Ints(res)
    return res
}

func dfs(land [][]int, sum *int, r,c, m, n int ){
   
    for _, v := range x{
        for _, vv := range y{
            if r+v < 0 || r+v >=m || c+vv < 0 || c+vv >= n{
                continue
            }
            if land[r+v][c+vv] == 0{
                land[r+v][c+vv] = 1
                *sum += 1
                dfs(land, sum, r+v, c+vv, m,n)
            }
           
        }
    }
    
}

java 解法, 执行用时: 12 ms, 内存消耗: 76.8 MB, 提交时间: 2022-11-29 12:27:09

class Solution {
    public int[] pondSizes(int[][] land) {
      List<Integer> list = new ArrayList<>();
      int temp;

      // 遍历矩阵每个元素
      for (int i = 0; i < land.length; i++) {
        for (int j = 0; j < land[0].length; j++) {
          temp = findPool(land, i, j);
          if (temp != 0) list.add(temp);
        }
      }

      // 第一种List<Integer>转int[]
      // int[] result = new int[list.size()];
      // for (int i = 0; i < result.length; i++) {
      //   result[i] = list.get(i);
      // }

      // 第二种List<Integer>转int[]，优雅且高效
      int[] result = list.stream().mapToInt(Integer::valueOf).toArray();

      Arrays.sort(result);

      return result;
    }

    private int findPool(int[][] land, int x, int y) {
      int num = 0;
      if (x < 0 || x >= land.length || y < 0 ||y>=land[0].length||land[x][y]!=0) {
        return num;
      }
      num++;
      land[x][y] = -1;   // 如果为0，就转换为-1，避免重复搜索

      num += findPool(land, x + 1, y);
      num += findPool(land, x - 1, y);
      num += findPool(land, x, y + 1);
      num += findPool(land, x, y - 1);
      num += findPool(land, x + 1, y + 1);
      num += findPool(land, x + 1, y - 1);
      num += findPool(land, x - 1, y + 1);
      num += findPool(land, x - 1, y - 1);

      return num;
    }
}

python3 解法, 执行用时: 240 ms, 内存消耗: 20.3 MB, 提交时间: 2022-11-29 12:23:54

class Solution:
    def pondSizes(self, land: List[List[int]]) -> List[int]:
        n = len(land)
        m = len(land[0])
        rst = []
        def dfs(i,j):
            land[i][j]=1
            area = 1
            for (dx,dy) in [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)]:
                if dx>=0 and dx<n and dy>=0 and dy<m and land[dx][dy]==0:
                    area+=dfs(dx,dy)
            return area

        for i in range(n):
            for j in range(m):
                if land[i][j]==0:
                    rst.append(dfs(i,j))      
        rst.sort()
        return rst

python3 解法, 执行用时: 184 ms, 内存消耗: 19.2 MB, 提交时间: 2022-11-29 12:23:41

class Solution:
    def pondSizes(self, land: List[List[int]]) -> List[int]:
        n = len(land)
        m = len(land[0])
        deque = collections.deque([])
        rst=[]
        for i in range(n):
            for j in range(m):
                if land[i][j]==0:
                    land[i][j]=1
                    deque.append((i,j))
                    tmp_count = 0
                    while deque:
                        x,y = deque.popleft()
                        tmp_count+=1
                        for (dx,dy) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]:
                            if dx>=0 and dx<n and dy>=0 and dy<m and land[dx][dy]==0:
                                deque.append((dx,dy))
                                land[dx][dy]=1
                    rst.append(tmp_count)
        rst.sort()
        return rst