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

问题描述

面试题：

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

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

例如

[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

我建议的修改：

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

问题是：

就时间复杂度而言，最快的算法是什么？
使用带有秩的联合查找需要删除一个节点。这是提高时间复杂度的方法吗？如果是这样，是否有在 union find online 中删除节点的实现？

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

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

块切割树示例 1

切割顶点是顶点B。块切割树中顶点B的度数为2。

Sum（每个“块”顶点的基数）：2（A，B）+ 1（B）+ 3（B，C，D）= 6

总和（每个“切割”顶点的度数）：1（B）

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

块切割树示例 2

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

总和（每个“切割”顶点的度数）：2（C 和 D）

块切割尺寸：8 – 2 = 6，即 (A. B, C, D, E, F)。这里不用减一。

标签： algorithmgraphgriddepth-first-searchbreadth-first-search

解决方案

没有预处理：

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

请注意，O(V) = O(E) = O(num_row*num_col)。

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

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

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

预处理：

将原始矩阵视为图G，其中每个“1”代表一个节点，相邻节点与一条边相连。
查找所有连接的组件
构造 G 的一组块切割树（第 5.2 节）（也是此处、此处和此处）（对于G的每个连通分量一个块切割树）。施工：见这里。

加工：

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

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

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

如果此单元格是块切割树中的“切割”：
- 从块切割树中删除它
- 从每个相邻的“切割”顶点中删除它
- 将块切割树拆分成几个块切割树
否则（此单元仅是一个“块顶点”的一部分）
- 将其从“块”顶点中移除；如果为空 - 删除顶点。如果 block-cut-tree 为空 - 从树集中删除它。

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

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

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

问题描述

解决方案

推荐阅读