Bloomberg 岛屿题变体：按连通块大小统计岛数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版输入矩形 0/1 网格，1 为陆地，只以四邻接连通；题目未说明对角相邻是否算。
• 输出训练版用 {size:count}，若面试要求长度为 K 的数组，另按 1..K 映射，0 数量也要明确。

解题路线

1. 逐格扫描，只从尚未访问的陆地启动 BFS；入队时立即标记，避免同一格被多邻居重复入队。
2. 每个 BFS 累计该连通块 size，结束后 counts[size] += 1；返回所有大小的计数。
3. 先手算孤立点、两块同尺寸和长链；若要求 DFS 可递归但深网格可能栈溢出，显式队列更稳。
4. 题目输出 [2,0,5,0] 缺对应 grid，不能用它证明某种下标或 8 邻接解释。

手动走一遍

训练网格 [[1,1,0],[0,0,0],[1,0,1]] 有一块大小 2 和两块大小 1，返回 {1:2,2:1}；若按长度 2 的数组从 size=1 起，则是 [2,1]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter, deque


def islands_by_size(grid):
    """Count 4-connected land components by size; land is 1."""
    if not grid:
        return {}
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    seen = set()
    sizes = Counter()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or (r, c) in seen:
                continue
            queue = deque([(r, c)])
            seen.add((r, c))
            size = 0
            while queue:
                x, y = queue.popleft()
                size += 1
                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1 and (nx, ny) not in seen:
                        seen.add((nx, ny))
                        queue.append((nx, ny))
            sizes[size] += 1
    return dict(sizes)

复杂度

R×C 网格每格最多入队一次，时间 O(RC)，visited/队列最坏 O(RC)，大小计数至多 O(RC)。

易错点与追问

容易失分的边界

• 对角相连未澄清就合并。
• 在出队时才标记导致重复入队。
• 用题目不完整输出倒推网格。
• 把岛数与岛大小和混用。

继续深挖

• 如果网格稀疏怎么存？
• 若查询动态加陆地可否用并查集？
• 按 size 输出稠密数组还是字典？