将坐标设置为 1 后找到最大的

Question

面试题：

给你一个由 1 和 0 组成的网格。您可以任意 select 该网格中的任何点。您必须编写一个函数来做两件事：

如果您选择例如坐标 (3,4) 并且它是零你需要翻转那对一个。如果是 1，则需要将其翻转为零。
你需要return最大的连续区域最多的，即必须至少连接到另一个。

例如

[0,0,0,0]
[0,1,1,0]
[1,0,1,0]

我们有最大的区域是 3 个区域。我们有另一个只有一个的区域（位于坐标 (2,0)）。

你要找到一个算法来解决这个问题，你会多次调用那个函数。您需要确保您的摊销运行时间是您可以达到的最低时间。

My Solution which has Time Complexity:O(num_row*num_col) 每次调用此函数时：

def get_all_coordinates_of_ones(grid):
    set_ones = set()
    for i in range(len(grid[0])):
        for j in range(len(grid)):
            if grid[i][j]:
               set_ones.add((i, j))

    return set_ones

def get_largest_region(x, y, grid):

    num_col = len(grid)
    num_row = len(grid[0])
    one_or_zero = grid[x][y]

    if not grid[x][y]:
       grid[x][y] = 1 - grid[x][y]

    # get the coordinates of ones in the grid
    # Worst Case O(num_col * num_row)
    coordinates_ones = get_all_coordinates_of_ones(grid)

    while coordinates_ones:
       queue = collections.deque([coordinates_ones.pop()])
       largest_one = float('-inf')
       count_one = 1
       visited = set()
       while queue:
           x, y = queue.popleft()
           visited.add((x, y))
           for new_x, new_y in ((x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)):
               if (0 <= new_x < num_row and 0 <= new_y < num_col):
                   if grid[new_x][new_y] == 1 and (new_x, new_y) not in visited:
                       count_one += 1
                       if (new_x, new_y) in coordinates_ones:-
                           coordinates_ones.remove((new_x, new_y))
                       queue.append((new_x, new_y))
       largest_one = max(largest_one, count_one)
    return largest_one

我的修改建议：

使用按排名联合查找。遇到了问题。联合所有彼此相邻的。现在，当其中之一坐标被翻转，例如从零到一，我需要从它所连接的区域中删除该坐标。

问题是：

就时间复杂度而言最快的算法是什么？
使用 Union Find with rank 需要删除一个节点。这是提高时间复杂度的方法吗。如果是的话，有没有union find online删除一个节点的实现？

------------------------编辑-------------------- --------------

我们是否应该始终从总和（每个 'cut' 顶点的度数-1）中减去一个度数。这里有两个例子，第一个我们需要减一，第二个我们不需要减一：

Block Cut Tree example 1

切顶点为顶点B，块切树中顶点B的度数为2

总和（每个 'block' 顶点的基数）：2(A,B) + 1(B) + 3 (B,C,D) = 6

总和（每个 'cut' 顶点的度数）：1 (B)

块切割尺寸：6 – 1 = 5 但应为 4（A. B、C、D、E、F）。这里需要再减一

Block Cut Tree Example 2

总和（每个 'block' 顶点的基数）：3 (A,B,C) + 1(C) + 1(D) + 3 (D, E, F) = 8

总和（每个 'cut' 顶点的度数）：2（C 和 D）

块切割大小：8 – 2 = 6 即 (A. B, C, D, E, F)。这里不需要减一。

Answer 1

没有预处理：

翻转矩阵中的单元格。
将矩阵视为图形，其中每个“1”代表一个节点，相邻节点与边相连。
找到所有 connected components。对于每个连接的组件 - 存储其基数。
Return 最高基数。

注意 O(V) = O(E) = O(num_row*num_col).

第 3 步需要 O(V+E)=O(num_row*num_col)，这与您的解决方案类似。

You are to find an algorithm that will solve this where you will call that function many times. You need to ensure that your amortized run time is the lowest you can achieve.

这暗示您可以从预处理中获益：

预处理：

将原始矩阵视为图G，其中每个“1”代表一个节点，相邻节点与一条边相连。
查找全部connected components
构建block-cut trees (section 5.2) of G (also here, here and here) (one block-cut tree for each connected component of G). Construction: see here的集合。

处理中：

如果将“0”单元格翻转为“1”：

查找相邻连通分量（0 到 4）
删除旧的分块树，为合并后的组件构建新的分块树（可以进行优化：在某些情况下，可能会更新而不是重建之前的树）。

如果将“1”单元格翻转为“0”：

如果此单元格是分块树中的 'cut'：
- 将其从块切割树中移除
- 从每个邻居'cut'顶点移除它
- 将block-cut-tree拆分为若干个block-cut-tree
否则（此单元格仅属于一个 'block vertex'）
- 从'block'顶点移除它；如果为空 - 移除顶点。如果 block-cut-tree 为空 - 将其从树集中移除。

块切割树的大小=总和（每个'block'顶点的基数）-总和（每个'cut'顶点的neighbor_blocks-1）。

块切割树不像其他数据结构那样'well known'，所以我不确定这是否是面试官的想法。如果是 - 他们真的在寻找对图形算法有丰富经验的人。

将坐标设置为 1 后找到最大的

Find largest ones after setting a coordinate to one

algorithm

graph

grid

depth-first-search

breadth-first-search