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

Question

面试问题:

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

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

例如

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

我们拥有最大的区域，即 3 个区域。我们有另一个区域只有一个区域(在坐标 (2,0) 处找到)。

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

我的解决方案具有时间复杂度: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

我的修改建议:

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

问题是:

1. 在时间复杂度方面最快的算法是什么？
2. 使用 Union Find with rank 需要删除一个节点。这是提高时间复杂度的方法吗。如果是，是否有在线union find删除节点的实现？

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

我们是否应该始终从总和(每个“切割”顶点的度数-1)中减去一个度数？这里有两个例子，第一个我们需要减一，第二个我们不需要减一:

Block Cut Tree example 1

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

总和(每个“ block ”顶点的基数):2(A,B) + 1(B) + 3 (B,C,D) = 6

总和(每个“切割”顶点的度数):1(B)

block 切割尺寸: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

总和(每个“切割”顶点的度数):2(C 和 D)

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

Answer 1

没有预处理:

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

请注意 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.

这暗示您可以从预处理中受益:

预处理:

1. 将原始矩阵视为图 G，其中每个“1”代表一个节点，相邻节点与一条边相连。
2. 查找所有 connected components
3. 构建 block-cut trees 的集合G 的(第 5.2 节)(还有 here、here 和 here)(G 的每个连通分量一个 block 切割树)。施工:见here .

处理:

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

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

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

• 如果此单元格是 block 切割树中的“切割”:
  • 将其从block-cut-tree中移除
  • 从每个相邻的“切割”顶点中移除它
  • 将block-cut-tree分成几棵block-cut-tree
• 否则(这个单元格只是一个“ block 顶点”的一部分)
  • 将其从“ block ”顶点中移除；如果为空 - 移除顶点。如果 block-cut-tree 为空 - 将其从树集中移除。

block 切割树的大小 = sum(每个“ block ”顶点的基数)- sum(每个“切割”顶点的 neighbor_blocks-1)。

block 切割树不像其他数据结构那样“广为人知”，所以我不确定这是否是面试官的想法。如果是 - 他们真的在寻找在图形算法方面经验丰富的人。